Se você não se importar de instalar o Windows em seu computador, existe uma maneira de fazer isso.
Como você disse, o emparelhamento acontece via USB e só é possível no Windows. O que você pode fazer é emparelhar o teclado no Windows e transferir as informações de emparelhamento para o Linux. Há muitas informações sobre como "pareamento duplo" ou como fazer dispositivos Bluetooth funcionarem em ambientes de "inicialização dupla".
Isso funcionou para mim: link no Ubuntu 18.04 , a única coisa diferente que tive que fazer é adicionar uma chave adicional não mencionada nesse guia (mas mencionada nos comentários): IRK e definir o tamanho do enclave como 16.
Veja como se parece o meu arquivo de informações, para referência:
[General]
Name=BTLE Keyboard Fingerprint ID
Appearance=0x03c1
AddressType=static
SupportedTechnologies=LE;
Trusted=true
Blocked=false
Services=00001800-0000-1000-8000-00805f9b34fb;00001801-0000-1000-8000-00805f9b34fb;0000180a-0000-1000-8000-00805f9b34fb;0000180f-0000-1000-8000-00805f9b34fb;00001812-0000-1000-8000-00805f9b34fb;d4e3e3eb-a4ae-4193-bbf8-c769980abfe0;
[DeviceID]
Source=2
Vendor=1118
Product=2067
Version=274
[IdentityResolvingKey]
Key=40DA574571378A18D19EECB0B6814F2D
[LocalSignatureKey]
Key=9514799E99500FAACE427153D3345C63
Counter=0
Authenticated=false
[LongTermKey]
Key=467D87EB169591378DB06F3E14C43FFD
Authenticated=0
EncSize=16
EDiv=41809
Rand=8310545922518117455
[ConnectionParameters]
MinInterval=6
MaxInterval=6
Latency=60
Timeout=200