watchOS 10 RC update.
I had my Apple watch on 10 beta 8, with the companion app stuck in the location problem described above. Upgraded both iPhone & watch to the RC releases, uninstalled the apps, and installed & run iPhone app from Xcode, went to watch app and installed it on the watch, started there. Same problem, watch app still stuck in the location request. Killed+uninstalled both apps, reset location permissions on iPhone, restarted the iPhone (not the watch), did the installation process again (Xcode run to iPhone + watch app to reinstall on the watch), and it worked.
I noticed that for companion apps, location permissions are listed on the iPhone (Settings > your app, location is first line) & not on the watch itself. When the problem occurs, that first location line is absent. My hypothesis is that something breaks the location permission of our app that reinstallation of both apps can't fix & a global reset of location permissions (+ Face ID access for all apps) is the only way out.
About what breaks it, I don't know. It seems that for companion apps, the iPhone is handling the permission for both devices. I suspect that maybe installing a new version of the app on iOS from Xcode while the watch app is running might be cause, or something similar (like running the watch app directly from Xcode with the iOS still at a previous version).
It is not clear if that can occur to end users that only install through App Store (no Xcode run). But if you happen to create the bug on your device, no app uninstall, no TF install, no App Store reinstall can fix it by itself.
Not too sure where to go from here. Would be interesting to know (for those with shipping apps) whether end users report such issues or if it is limited to those who run it at least once through Xcode. It is also possible that the problem won't reappear starting from the RC (did not experience it yet - will report if it's back).