Can't connect my Pixel 2 to any headphones device

[Android Central Question]

Headphones are not showing up on the phone's bluetooth available devices list at all, unlike any other device. I've tried with two different headphone types. While connecting to other phones and laptops are ok.

I've tried many solutions starting from restarting both devices till reset the Bluetooth settings

 

[Rukbat]

Have you put the headphones into discoverable mode? You can't pair them if they aren't. If they already are, see if you have a "paired devices" line in the Bluetooth screen.

 

[B. Diddy]

Welcome to Android Central! Also, you're tapping the Pair New Device option in the Settings>Bluetooth​ menu, right?