i've had trouble pairing my bluetooth as well. instead of going to bluetooth explorer, go to settings > connections > bluetooth > add new device (even if its in the list still click this). after it finds the headset go through all the settings then when your done tap and hold where it says S9 (or whatever your headset is called) then choose set as wireless stereo, then it will say your device wants to connect. if it says the passcode is invalid try again and it should work. while this way of pairing my headset can take around 5 min. or more, its the only way it seems to be working.
i am not sure if your phone is showing the same symptoms as mine or not, but if this is a common problem then i hope someone smarter than me can fix it, becaue the way i have to set it up is a real pain.