Something to investigate - the version of OS on your device.
This occurred to me before but I thought I’d covered it because I’ve always used 2 different devices iphone and iPad. iPhone is 26.4.2. iPad is 18.7.9. Since they were different but both failed to connect I put aside that idea.
But this morning I dug out an old smashed screen iPhone running 15.8.4 and it connected first time after I turned Bluetooth off / on.
A couple more tries and still worked.
This is not a comprehensive proof of anything. It might just be lucky coincidence. I’m out for a while now, but if it regularly connects when I get back home for more testing, it’s the start of identifying the root cause.