I know the question is old but I keep bumping into it so I'm sharing 2 possible solutions for anyone else struggling:
- In the screenshot in the question just put in a PIN on the available keyboard and press Connect. Then on the bluetooth keyboard enter the same PIN and press enter
(as suggested by someone else on this chain)
- From a Powershell / Command window run DevicePairingWizard.exe to pair the device. This thankfully works for me even on a laptop where I have no admin rights
I hope this helps someone in the future.