Aircraft performance is not usually the problem, as extrapolation rules for higher-than-tested altitudes are well established. The limited takeoff weights are generally a good indication of the poor capabaility at these altitudes.
Really, the tricky bit is testing and certifying systems, particularly the ECS and powerplants. The certifying authority for the aircraft type is responsible for giving the aircraft its ticket to actually operate from high elevations, and then the local authorities may also have their own say in operations on particular routes.
Generally, the manufacturer must test at the desired elevation, or close to it, to demonstrate succesful operation. In addition, a fair amount of analysis is required to back up the case. Then, demonstrations from the actual airports are the done thing.
Take Airbus and Boeing for instance. To operate from Bangda, Tibet (approx 14200ft), both companies had to actually go there and demonstrate to the customer that it all works, and this was on top of the certification effort.
As was pointed out, masks dropping, along with trouble opening doors, engine operability, engine margins, actual ability to set power, demonstrated capability to fly unusual procedures without increased pilot workload etc have to be convincing to authorities and customers alike.
It's not a 5 minute job!