This is really two questions
- Why does Paro need special certification?
- Why doesn't Princess Juliana need special certification?
I'll answer both, which I think answers your overall question about "Why does Paro need special certification but Princess Juliana doesn't?"
Why does Paro need special certification?
You've mostly answered this, it's because it's high up and in challenging terrain.
- Less dense air at higher altitude requires a higher groundspeed on landing
- The nature of the valley means there are almost constant, unpredictable gusty crosswinds. Nasty at any airport, but worse here due the terrain
- The runway is short considering the terrain - it's not a short runway per se, but it increases the chance of needing to go around, which is tricky
- It's very hard to go around compared to most airports - you need to know exactly where you're flying, rather than just maintaining runway heading and climbing out until given other instructions
- You're in mountainous terrain (lots of things to crash into!)
- The approaches are visual - added to the fact it's a difficult approach in the first place. The lack of ILS makes landing harder, you don't know if you're on the glideslope or not
- And this has been covered by the other points, but it's worth repeating.... There are 5000m high mountains all around it, dramatically limiting approach and escape options
There's real no question that Paro is a difficult airport to land at: it requires an unusual approach, special awareness, a higher than normal level of skill and is very unforgiving.
Why doesn't Princess Juliana need special certification?
Because although the videos look very dramatic, simply put, it's not very hard to land at. The runway is short compared to most international airports, but it is long enough. Once the runway is beyond the minimum required for an aircraft, it's long enough and that's all there is to it. A longer runway may in theory require fewer go-arounds, but a "long enough" runway doesn't make landing there hard
Other than the runway length which, as just described, isn't actually a problem, there's nothing too difficult about it:
- It's got nice, open approaches at each end
- Clear glideslopes
- It's at sea level, maneuvering is about as easy as it gets
- It's an Instrument approach, you can make it in almost any weather
- There's loads of time/space to make a missed approach and go around
- There are no 5000m mountains around it, just lots of sea - and if you crash into the sea, you would have crashed into the ground anywhere else, so this isn't any more difficult than any other airport
It's not the easiest airport ever to land at, but it's not unusually difficult... although it certainly looks very dramatic, with the videos of Airliners sweeping over the top of a beach and road. The important thing to note is that the beach and road are both well below the glideslope - aircraft only really care about obstructions near or above the regular glideslope.
Although that beach approach looks crazy it actually poses no problems whatsoever for an aircraft - the jets are still comfortably on the glideslope: they don't care if the last section before the runway is grass, sand, a road etc, they were always going to be at that altitude.
You since edited the question to ask how they get this certification - you'd have to go and work for Druk Air (Royal Bhutan Airlines). Until recently they were the only carrier who flew into or out of the airport, and they work with the Bhutan government to certify pilots.