For some reason, this didn't work with the standard GUI bluetooth tools, so I did the following
- Run the command-line bluetoothctl tool
- type "agent on"
- type "scan on"
- press the button on your keyboard, the light should flash if it's not paired with anything else
- type "devices" (this shows the list of devices)
- type "trust xxxx" where xxxx is the keyboard MAC
- type "connect xxxx" where xxxx is the keyboard MAC
- type "pair xxxx" where xxxx is the keyboard MAC