One option is essentially a programming test framed as a first quick milestone. Say the app is for taking and sharing photos and has a $10k budget. Start with a milestone for an app with a single button. When the button is tapped the user can take a photo using the built-in, default camera view. Price this milestone at $300 or some other small fraction of the total cost.

If the contractor quickly sends you something simple that works without too many lines of code then you have a decent signal that the skill level is sufficient. Anything else (slow response time, app doesn't work, below expectations code quality etc) and you have a decent signal that the skill level is insufficient. In this case just pay out the first small milestone, thank the contractor, cancel the project and try someone else.