Is anyone aware of what the operating temperatures would be for a situation where the Mark III would be taken to an elevation of almost 4 km (2.5 mi) and used straight out of the bag?
I have no idea how the camera would do, but if you mean going straight from sea level by plane or land humans don't do well at all. Google "altitude sickness" and read up on acclimatisation. It can be fatal.
At a rate of altitude increase safe for humans (days), your camera will have time to equalise its temperature with the outside. The pressure, of course, is instantaneously equalised, since your bag is not a pressure vessel. I think we can assume that a 5D Mark III will not explode at 4000m. In fact I'd guess it's been built to handle shipping by air at 10,000m.