I’ve finally been able to pair it following instructions found there: http://askubuntu.com/questions/761947/ubuntu-mate-16-04-doesnt-ask-for-pairing-code-to-connect-apple-keyboard
If I use bluetoothctl in command line, pairing works. It looks like that when using the GUI tools, the PIN/password is not sent and the pairing fails.
I’m not sure why it works differently with the phone.