The answer to your questions lies in one word:
Air
At high altitudes there ain't much of it.
With regard to auto versus manual starts, go to your manuals and see what they say.
If your aircraft uses bleed air to start, you may have to get as much load off of the APU as possible to start one engine and then use a cross bleed configuration to start the other.
Hope this helps.