You need to disable "Bluetooth low energy", then follow these core steps:

1. Make sure the headphones are in pairing mode.
2. Pair with System Settings > Bluetooth. On 16.04 I had to choose "proceed without pairing" and enter the PIN "0000"
3. Select & test the headphones in System Settings > Sound. Choose High Fidelity Playback (A2DP Sink).

Do you need DevOps-experts?

Your development team has a full backlog? No time for infrastructure architecture? Our DevOps team is ready to support you!

• We build reliable cloud solutions with Infrastructure as code
• We are experts in security, Linux and databases
• We support your dev team to perform

Read more Show archive.org snapshot

I also had to install a package with sudo apt-get install pulseaudio-module-bluetooth and load it with pactl load-module module-bluetooth-discover. Put the latter command into ~/.bashrc or you'll need to run it after each boot.

Troubleshooting

• If you can see the headset in your Bluetooth devices list, but it won't succeed to connect: Remove the device and search for it again. It should successfully establish the connection.

Resources

• https://askubuntu.com/a/833323/427179 Show archive.org snapshot
• https://askubuntu.com/questions/801404/bluetooth-connection-failed-blueman-bluez-errors-dbusfailederror-protocol-no Show archive.org snapshot