I've got a same issue with a WearOS device. I gave up after a few cycles of re-pairing and forced device wipe.
There's an r/GooglePixel thread with a similar issue where the Google support responded. Maybe we could make some noise there for some attention.
I did a small research where does "For your security, forget this device, then pair it again" come from. It seems that this string is defined in the strings.xml file under bluetooth_key_missing_message
key. My current guess is that the security key for the paired device is getting wiped somehow on the phone (dunno, why). When this happens, there's no coming back – "device pair" is no longer usable and the only possible action is to remove the entry itself.
Perhaps I've got it wrong. That's how I understand this issue for now.