Magic I've tried everything: clearing cache, updating Play Services, reinstalling...
You most probably didn't need to do any of this. This is most probably caused by the apps using the Play Integrity API in the Play Store listing. Try to check your device's Play Integrity verdict, it should be at least 'basic'; you can check it either from inside the hidden Developer Options in Google Play Store (not the same as the Developer Options in Android and no need to enable it for this) or using a dedicated app.
If your device doesn't get at least a 'basic' verdict, try allowing the Google Play services app to perform DCL via memory, then clear the cache for Google Play services and reboot, and try checking again. If your device gets at least a 'basic' verdict, then there's nothing more you can do.