I wonder what it is. The remove permissions, reset both devices, add permissions does seem to fix it, at least this time. I would argue that it's not really random though as it's only WOD that is having an issue so I would guess there is some bug that is being triggered either by WOD or by my specific devices configs and settings since it's so repeatable. Hoping the PB of 14.2 drops soon and that it fixes this though. I adore WOD so not being able to use it is killing me this past week.
I am glad that fixed it. Maybe it is the long standing rare bug in watchOS 6 that has somehow become more common in watchOS 7. It's good to know there is a fix that is not too drastic.
There is nothing that WOD could be doing that is different to any other app. It just asks to get the heart rate and watchOS/iOS do the rest in terms of permissions. That is by design by Apple - they control the permissions for obvious privacy reasons.
Hopefully this fix will be more permanent than the last one. As far as I know it was a permanent fix for the rare bug in watchOS 6, but I think I only ever saw that 2 or 3 times so I don't know for sure.