I have an Asus Zenfone running Android 6.0.1. and a Bluetooth headset (Philips SHQ6500) that I had paired but accidentally selected the forget option. Now it's impossible to re-connect it because the phone cannot see the headset at all. I restarted both devices and did a hard reset for network settings but the problem persists. Googling didn't help so I'm stuck at the moment.
I faced a similar situation. Following steps worked for me. Some of the steps might be redudent.
1) restart your phone
2) reset network settings (Setting> back and restore )
3) change the phone bluetooth name. (I assume this is the solution)
4) set the bluetooth device in pairing mode (long press the power key).
And it worked for me. Probably, executing only step 3 would be sufficient.
I hope I saved your precious 30 minutes:)