I am writing this post because I forgot to bookmark the forum thread where I originally read the solution. So I backtracked using the .bash_history file, and compared it with an original version.
Start by unpairing the keyboard from your computer. Then open
/lib/udev/rules.d/97-bluetooth-hid2hci.rules
Remove
KERNEL=="hiddev*",
from the following line
KERNEL=="hiddev*", ATTRS{idVendor}=="046d", ATTRS{idProduct}=="c70[345abce]|c71[3bc]", \
so it looks like
ATTRS{idVendor}=="046d", ATTRS{idProduct}=="c70[345abce]|c71[3bc]", \
and reboot and pair it!