Your title talks about connecting, but the question body talks about pairing. These are two different things.
When you pair a Bluetooth peripheral (such as a headset) with a central (such as a phone or PC), the two devices swap cipher keys that allow them to keep their radio transmissions secure in future. Once they're paired, they remember the cipher keys forever. They can later connect to each other without having to pair again. If you like, pairing is like swapping phone numbers, while connecting is like calling their phone.
Normally, if you leave Bluetooth turned on on a phone or PC, it will keep looking for peripherals it has paired with before, and automatically connect to them as soon as they're in range. This makes it a lot easier for you, because you just have to turn on the headset and it's immediately ready to use. In this case it seems to have caused some confusion, though.
Any Bluetooth device can pair with several devices: exactly how many depends on the device, and how much memory it has. Some very cheap headsets may only pair with one, but usually they can remember up to a dozen pairings. When you pair with too many devices, it just forgets the oldest pairings. (Like erasing your old friends' phone numbers from your phone book to make space for newer friends.) Bluetooth centrals can pair with lots of devices at once.
Just like you can only call one phone at a time, a Bluetooth peripheral can only be connected to one central at a time. It needs to disconnect before another central can try to connect to it.
In your case, it looks like the headset was connected to the PC when you tried to pair it with your phone. This couldn't work, because a second central can't connect to the same peripheral. When you unpaired it from the PC, the PC also disconnected, which then made it available for the phone to connect to. In practical terms, what this means is that if you want to keep using it for both, and you want to control whether the PC or phone connects to it, either keep unpairing and pairing again (like you already did), or turn off Bluetooth on the PC when you want to connect with your phone (and vice-versa).
