GraphenePen
Try reverting the location permissions given to Play Services, Play Store and Framework, because with the default system settings for location, those apps don't need location permission. And then try stepping outside with a view of the sky so the phone can get a satellite fix.
Here is a summary on OS location settings made by the GrapheneOS account on Discord, which might bring clarity:
there are 2 sensible configurations:
1) default: Location request rerouting enabled, Play services Location and Nearby Devices permissions disabled (unless you need Nearby Devices for something else), Play services network location accuracy disabled, Bluetooth and Wi-Fi location scanning toggles in Settings > Location disabled
2) if you want to use Google's network-based location service to detect location based on cellular, Wi-Fi and Bluetooth devices: Location request rerouting disabled, Play services Location and Nearby Devices permissions enabled, Play services network location accuracy enabled, Bluetooth and Wi-Fi location scanning toggles in Settings > Location enabled
Settings > Apps > Sandboxed Google Play has a section where it gives configuration recommendations and warns about a mismatch with these