It paired after a few attempts, but would immediately disconnect. Installing the a2dp package as per the first post in this thread resolved that issue though.
I can connect my tablet to the Echo Dot and stream audio to it without issue.
When you say Audio output should be PulseAudio or Bluetooth, I have gone into System Settings > Audio output > Audio output device and selected ALSA: OSMC streaming to Bluetooth speaker / headphones. Is this correct? Or should I configure it somewhere else?