This content may not be relevant as of 4/22/20. It is still provided for historical purposes
To get Bluetooth audio devices (bluetooth speakers, headphones, etc.) working under Linux, you will need to install the Bluez (Bluedevil also for KDE) packages from your distro's repo.
If you have problems, or can't get anything to pair, try consulting this page: https://wiki.archlinux.org/index.php/Bluetooth
Check the output from bluetoothctl first when pairing using bluetoothctl to diagnose your error. If you're using laptop power management such as PowerTOP or TLP, be sure to allow bluetooth cards to be used when on battery or AC power. Check your config files (TLP) or disable bluetooth shutoff in --auto-tune (PowerTOP) and restart your computer (to reload the configuration).
hciconfig hci0 sspmode 0 as the root user (sudo). If this won't work (command not found, etc), hciconfig may not be on your system anymore due to it being deprecated.
Then in a terminal, type
sudo hciconfig hci0 reset to reset your bluetooth pairings and the settings that may have been corrupted and try reconnecting again (using bluetoothctl or the bluetooth menu under system settings).
Muffled audio quality, disconnects within a few seconds
Go to your bluetooth headset settings and select A2DP instead of HSV. (Bluetooth speakers also exhibit this same issue, usually if they have a mic for speakerphone calls.) Bluetooth is recognizing your device as a headset rather than an audio stream. If you want to make calls with the microphone, switch this back to HSV (it may not work though, as audio will still play muffled). The headset option is made to work on your phone, and not your computer.
KDE Plasma 5.12: Click on the volume icon in the system tray, then click the sliders at the top right to go to the audio settings. Click on "Audio Volume" tab > "Advanced" sub-menu > your headphone's bluetooth name > Profile: "High Fidelity Playback (A2DP Sink)" OR "Headset Head Unit (HSP/HFP)".