After much searching high and low I found this youtube video that solved my issue.
In a nutshell:
It seems that trying to pair with the default pin (0000) does not work.
You need to set a different pin by pushing the numbered buttons on your console (mine look different to the video, but they work the same).
I set a pin of 1111 by pushing the buttons 1 ...