> Typical issue - I want to download an app that's not on available "in my country" - because I'm on a holiday and want to try some local app,
The solution here is just to get rid of artificial country limitations which make some users download APKs. None of those make sense in the online world anyways.
Requiring company verification helps against some app pretending to be made by a legitimate institution, e.g. your bank.
Requiring public key registration for package name protects against package modification with malware. Typical issue - I want to download an app that's not on available "in my country" - because I'm on a holiday and want to try some local app, but my "play store country" is tied to my credit card and the developer only made it available in his own country thinking it would be useless for foreigners. I usually try to download it from APKMirror. APKMirror tries to do signature verification. But I may not find it on APKMirror but only on some sketchy site. The sketchy site may not do any signature verification so I can't be sure that I downloaded an original unmodified APK instead of the original APK injected with some malware.
Both of these can be done without actually scanning the package contents. They are essentially just equivalents of EV SSL certificates and DANE/TLSA from TLS world.