When I have had this problem, it was always because my headset was paired to another device, probably my iPhone. I needed to explicitly unconnect from the current device before I could connect it to the Mac.
Likewise, I need to disconnect it from the Mac before I can connect it to my phone.
Some bluetooth devices can be connected simultaneously to more than one device, I hear. I wish I had one of those.
Now, what I want is to teach my Mac not to connect to the headset automatically, but only when I ask it to connect. (I don't want to remove it from the list of paired devices, because I do sometimes connect it.)