Additionally, not all malware needs to escape a sandbox. For instance, there are a bunch of fake apps that simply capture credentials, or that make expensive phone calls or texts.
A well-run store that can run tools against images is a decent first line of defense against malware. A store also provides reliable information about code publishers. These are not a complete defense, but they appear necessary.
The iOS model (and now Android model) of prompting for permission when the app first tries to use it is much more solid. If an app requests access to your contacts for no good reason, you'll get a fairly obvious prompt and you can say no. There's still some trouble with getting users to pay attention, but it's a lot better.
I don't see how this makes a store appear necessary. Android doesn't allow sideloading by default, and iOS can now sort of sideload apps using the new free signing stuff Apple put out. The limits on the number and duration of sideloaded apps make them impractical for selling legitimate software, but are no obstacle to malware.
In any case, malware is best prevented by strong sandboxing. Forcing everyone to go through the store does approximately nothing to fight malware.