I've updated the conclusion to better reflect that at the end of the day we still have to trust some third-parties, and this is where Open Source comes into play to bring transparency and accountability about what runs on our devices.
Of course, it is those same stores that issue the certs used for "trusted" verification, so they could reissue a new one, resign accordingly and noone would know unless they manually verified the cert with the developer.
Maybe that shouldn't be a thing ;)
But even then you need to trust the device to actually execute THAT bundle, of course... And even if it did, it could change its behaviour at runtime.
Dont forget you are also trusting many layers below the app itself: Hardware design and manufacture, device manufacturers, distributers and vendors, the OS (and the 3rd party libs they depend on) developers and distributers, the underlying application libs, frameworks and runtime, the application notaries and distributers, etc. At any point there could be bugs/vulnerabilities/backdoors/etc.