Something worth trying. This may not work, but it is something I had to do with my car stereo.

Don't invoke the pairing routine on the Arduino. (If you wired up a button, don't press the button.)

I've found that with some devices you don't do the pairing from both devices. For devices with interactive touchscreen UI's, you just do the pairing from the touch screen and don't touch the device you're pairing with.

With my bluetooth headset, I have to invoke pairing mode on both devices because neither one has a touchscreen UI. But on the car stereo, I just do everything from the car stereo screen.

Try that.