This applies to most bluetooth headphones under Linux, with Dell XPS 9550 laptops (well, probably to other systems using a broadcom BT chip).

Problem: If I went to the Bluetooth settings in Gnome, I could enable scanning, but my headphones would not appear in the list of available devices. I made sure that I reset the BT pairing completely on the headphones, and then set them in pairing mode. To double-check, I re-paired them with my phone.

Lead: Ubuntu Bug 1589889 describes a similar situation, and recommends installing a specific firmware. Also found this stack exchange post.

Solution:

1- Find the exact broadcom device ID

# lspci -nnk | grep -iA2 net; lsusb; rfkill list all; dmesg | egrep -i 'blue|firm'
[...]
Bluetooth: hci0: BCM20703A1
bluetooth hci0: Direct firmware load for brcm/BCM-0a5c-6410.hcd failed with error -2
Bluetooth: hci0: BCM: Patch brcm/BCM-0a5c-6410.hcd not found

2- Download the firmware

$ wget https://github.com/winterheart/broadcom-bt-firmware/raw/master/brcm/BCM20703A1-0a5c-6410.hcd
# cp BCM20703A1-0a5c-6410.hcd /lib/firmware/brcm/BCM-0a5c-6410.hcd
# chown root.root  /lib/firmware/brcm/BCM-0a5c-6410.hcd

3- Reboot (I could not figure what to restart to avoid a reboot)

The device should now pair as expected. Once paired, you may also need to go to the sound settings and select the headphones as the default sound device.