Isso parece ser uma "solução" hacky, na melhor das hipóteses, mas consegui conectar o dispositivo
# bluetoothctl
[bluetooth] remove <device>
[bluetooth] power off
[bluetooth] power on
[bluetooth] scan
[bluetooth] pair <device>
[bluetooth] trust <device>
[bluetooth] connect <device>
Note que eu tentei a rotina de remover / escanear / parear / conectar sem ligar / desligar algumas vezes, sem sucesso, então isso pode ser fundamental.