Можно попробовать сделать все через консоль. Откройте терминал и выполните:
$ sudo bluetoothctl
По порядку последовательно введите команды:
[bluetooth]# power on
[bluetooth]# agent KeyboardOnly
[bluetooth]# default-agent
[bluetooth]# pairable on
Далее, включите ваши наушники и выполните:
[bluetooth]# scan on
Появится нечто вроде:
[NEW] Device 79:CB:29:XX:XX:XX Wireless Headseat
Далее, скопируйте адрес устройства и наберите:
[bluetooth]# trust 79:CB:29:XX:XX:XX
После чего
[bluetooth]# pair 79:CB:29:XX:XX:XX
Далее подождите несколько секунд и все должно заработать