Start all-manual. Perhaps you only do it with a subsection of applications. Pay an extra fee and you get "certified" with special app placement. Then you start all-manual. You look for the people who are the best at finding issues, and pair them with programmers, and make the tools for the things that are gruntwork for them.
Build more and more tools, and you pull more and more people into the program as you build more and more intelligence into the machine.
Let the humans do the NP-hard portions. I'm sure this is what Apple has to be doing behind the scenes.
Human reviewers today, but once the training set is large enough you can start to let computers take over with human reviewers reviewing the lower certainty cases until the certainties rise further.
If an app takes days to make, requiring 5 minutes extra review effort to get it whitelisted seems fine.
A non-prohibitive barrier to entry wouldn't be a big issue, as users in general want stricter filters that mean less shitty apps instead of looser filters that mean simply more apps.
AI and machine learning are most effective these days when they help assist people (flagging potentially malicious code, bubbling up anomalies, etc.), and it isn't that expensive to get a pair of eyeballs to double check conclusions!
Manual prompts to users are a great way to develop training data and being able to distribute them at scale to millions of users means you can develop training data in very short order.
Automated tasks are not good at outsmarting humans. When you want to review a human's work for security, you need humans somewhere along the process.
Automation can help those humans do their jobs, but it's simply not a solution here.