> There's clearly a selective advantage for some of those 'configurations', but how many generations would it take for each genetic mutation required to make a lichen katydid or an orchid mantis to converge?

If you pose the question like that with the posteriori knowledge in mind, then yes, these configurations are highly improbable. I think another question that could be asked is: How many generations would it take for some mutations to produce some camouflage effect in some of the millions of existing species? Surely some mutations​ that produce camouflage effects will happen.