The hypothetical craft with the 250lb payload has a wingspan almost as wide as a 747's.

Aerodynamic lift (in Newtons) is proportional to airspeed and invesely proportional to air pressure. So is aerodynamic drag. This holds true up to the transsonic region; ~800 kph of true airspeed. As long as you're subsonic, it's sufficient to have the same amount of thrust as at low altitudes, and you'll keep flying at the speed required for lift >= aircraft weight.

Granted, this will require proportionally higher propeller RPM, but with electric engines this is unproblematic. You'd get in trouble with hydrocarbon engines though, since you need the same amount of oxygen to generate power. So at altitude, you'd need a turbocharger or similar machinery.