Dwight, good to hear from you! Before I get into Bolivia, make sure that you take the Santa Theresa route if you are going to Machu Picchu.
As far as elevation, if you're going to Bolivia, it's only going to get worse. Yesterday I rode 330 miles and it was all above 12,500 feet. Some of it was over 14,000 feet. If you are going to do the death road, you'll go over a pass that's 15,200 feet tall! At this point, I think the only thing you can really do to help yourself is to lay off the smokes and booze for a while.
Here's the skinny on fuel: Bolivians pay about 3 Bolivianos per liter; all forigheners pay three times that amount! The Bolivian government doesn't want people crossing into Bolivia, buying a bunch of gas on the cheap, then heading into Peru or somehwere else and selling it for profit on the black market.
Now, there's a pretty easy way to get around this. You won't get it as cheap as the Bolivians do, but it won't cost three times as much either. To make this work, you kind of need to be able to speak a little bit of Spanish.
Pull into the gas station (make sure it's a small less devolped one) and ask them how much the gas is. If you are lucky, they'll just give it to you at the normal price. Most likely they won't. If they tell you it's three times as much, just laugh and tell them that you paid 5 Bolivianos at the last gas station.
If they point at the survaillance camera, just tell them it's okay and that nobody will know, it'll just be "our little secret". Also, tell them they don't have to do all the paperwork and they don't need to give you a recipt. This should let them know that your willing to deal and hopefully they'll be in the barganing mood. They may want you to pull out of sight of the camera and fill up your bike using a jerry can or even empty coke bottles, but that's a small price to pay for the money you are saving.
Essentially, you're bribing them. You get gas cheaper than you normally would, and they get to skip the hassle of filling out paperwork, plus they get to pocket the difference in price. I'd say that's pretty win win. This little proccess has worked every time with me so far.
Hope that helps! Just went and rode in the water on the Salar today....epic! You've got to do it! I'll be out in the desert for the next few days on my way to chile, but if you have any other questions I'll try and get back to you as soon as I can.