I had some trouble connection my new Teufel Rockster XS (actually not a headset but a portable speaker) with my Debian notebook. Pairing worked without any problem but connection to the audio sink of the speaker -- to actually stream audio to the device -- returned the error:

Connection Failed: blueman.bluez.errors.DBusFailedError: Protocol Not available

The root cause was a missing package; so I installed it it with apt:

$ apt install pulseaudio-module-bluetooth

After installing the package I made sure the module is loaded and restarted the bluetooth service (be aware that all current connections will be terminated).

$ pactl load-module module-bluetooth-discover
$ systemctl restart bluetooth

You should also make sure the module is loaded after reboot. If the following command returns sensible information that should be the case.

$ grep bluetooth /etc/pulse/default.pa

I re-paired the device and could connect to the audio sink eventually.