I don't think there's enough pressure differential in the Earth's atmosphere to cause the bends. As previously mentioned, underwater you can experience many atmospheres of pressure. In air, you have just the one (obviously). That shouldn't be enough to affect blood-gas levels hugely. Take a look at the Stratos jump - Felix Baumgartner jumped from 128,000 feet, at which point the ambient pressure is about a third of one percent of what it is on the ground. Baumgartner went from that to full atmospheric pressure in nine minutes - not instantaneous, but definitely not gradually enough to count as the rest stops that deep-sea divers do to avoid the bends.
I saw the video and heard the commentary, he was in a SEALED suit like a diver's suit or spacesuit when capsule depressurized and he walked out and jumped. I don't know what point he took off the helmet, but he obviously did before he landed.
The problem here isn't the bends, but I find it hard to believe you could survive long in 1/3 of 1 percent of sea level air pressure, even if breathing pure oxygen. With pressure that low, there's not much oxygen entering the lungs.
In summary, I reckon you could teleport anywhere without worrying too much about altitude - equalise your ears when you arrive, take a few deep breaths if you've gone up, breathe gently and slowly if you've gone down, and take it easy for a few minutes.
You could transport into a sealed container with the air pressure matched to where you came from, and it then slowly decrease or increase pressure (over seconds or minutes, depending on how great the distance is) to match the location.
Other than that, the biggest danger you have from extreme altitude changes is finding out that you've teleported somewhere with no ground beneath you. Interesting side issue there: if you find yourself in mid-air, and teleport away, do you keep your speed?
This is similar to the discussion of Larry Niven's transporters - If you're transporting more than a few miles, the transporter needs to compensate for the different direction of motion of different points on Earth. If it knows how fast you're going, it can compensate for that too so that you're standing still at the end of the transport.