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!