Apple Wireless Keyboard - How to fix Windows 8.1 issue?

Question

Bluetooth

I'm trying to connect an Apple Wireless Keyboard (A1314) to a Windows 8.1 computer (not a poppy with bootcamp, but a regular Windows PC). Windows sees the keyboard, but when trying to connect directly, it gives the error "That didn't work. Please make sure your device is discoverable." In the Russian version, it also sounds like "It didn't work ..."
The keyboard is 100% working - it connects perfectly with OS X. Batteries are alive. I tried two different Bluetooth key fobs - one Broadcom, the other some kind of Chinese non-name. Both are on standard drivers from Windows 8.1, which are recommended for connecting this keyboard. Keychains are also 100% both working. I didn’t install the driver on the keyboard itself, but, as I understand it, it needs to be installed after its definition in order for Fn-combinations to work, etc.
I dug Google, there are people with similar problems, I did not find a solution.