You don't say which Plantronics headset you have. I did reset my S5 recently and ran into some difficulty pairing my Jawbone bluetooth headset. In my case, it was simply because I wasn't doing it right. After much frustration, I finally consulted the instructions that came with the headset and found, much to my embarrassment, that I simply needed to turn off the device, then hold down a particular button and power on the device while holding down the button. As soon as I did that, my S5 popped up a field for the password to be entered and that's all it took.
I don't know about your device's problem, but it may be something just as simple.