Mark,
The carb can't be legally re-jetted - IF it's in Calif.
That said, if you do go that route, make certain the tech doing the work knows, REALLY knows, what they are doing. Changing jets is no big deal - can always go back, but enlarging air bleeds by drilling isn't easy to fix if they are made too big.
Keep in mind though that any engine loses power at altitude, regardless of how well it is tuned. So, while you may gain a little more power by bringing the gas/air ratio back in line, I would not expect the engine to make the same power at 4500' as it does at sea level.
Dan