As one of the new proud 13 Pro Max owners, I was reading all up on this issue yesterday. Seems to effect most anyone who upgraded from one iPhone to another using the phone to phone transfer. Sounds like those who set it up using iCloud backup don't have the issue.
My own speculation is that something in that process of going straight phone to phone (which preserves more of your data and passwords than iCloud) screwed something up in the unlock key for the watch. But that's just a guess by me.
Lots of people indicate that wiping their new iPhone and restoring from an iCloud backup fixes the issue, but I've decided I don't care about it enough to have the pain of that step. I'll just wait for the Apple fix (my office doesn't have a mask mandate due to a lower number of employees, so it's only annoying at grocery stores)