My headphones (Plantronics) will connect to two devices at the same time. The controls interact with whichever was playing more recently, and an existing stream takes priority over a new one. So I can quite happily stop my music from my phone and start up a call from my laptop, then switch back, without re-pairing at all.

If I did need to re-pair, it's as simple as picking the phone from the phone or laptop's recently-used devices list. I usually only have to do that if the phone has decided it wants to keep talking to my headphones while I'm in the car. Pairing from scratch with the phone is as simple as holding the phone to one of the ear cups, but I've only had to do that once and I can't remember which one now.