Peguei este problema hoje na empresa que trabalho e consegui resolver fazendo o seguinte procedimento:
Abrir o services.msc
WIN + X > selecionar executar e digitar services.msc
Na janela que vai abrir, procure pelo serviço "DeviceAssociationBroker_" Descrição "Enables apps to pair devices"
Inicie este serviço, em seguida coloque o dispositivo Bluetooth em modo de pareamento e no menu de bluetooth do Windows clique em "adicionar dispositivo" em vez de conectar, desta forma funcionou.
O mesmo dispositivo vai ser listado mais de uma vez porém a nova conexão funciona.