You are unlikely to be camping, where you will use the stove, particularly high up. I routinely use a gas stove above 5500m and have no problems with it. You need to buy the cans with an isobutane and propane mixture for high altitude use. They are available in KTM and Pokhara. I'm not sure about the other places but I suspect that you could find them in Jomson. I use the MSR WindPro stove. 80/20 mixes seem to work best for me.
I sometimes use a MSR WhisperLite International. It is a good deal more fiddly but will burn all sorts of things. In Nepal I use it with, well filtered, kerosene/paraffin that is available in towns/large villages. I have seen Coleman fuel in KTM but have never really looked for it. The gas stove is much more convenient after a hard day.
I use an 8oz/220ml can, or 20oz / 0.59l of liquid fuel, a week below the snow line. I do not cook anything involved. Think pot noodles for two. It all rather depends on how much cooking you are going to do, which obviously depends on what you eat.
You cannot take fuel on an aircraft.