The search space is huge. And so is the solution space! It is huge also.
Especially with gene expression and splicing, there are many many ways to effect the same change. Uncountably many.
Also, gene expression is a very smooth landscape in sequence space, so it works great for evolutionary processes.
For these reasons, changing in gene expression by mutations is very very easy to do. We regularly see this happen even in human time scales. We see it in bacteria, cancer, in livestock and dog/cat/horse breeding programs. We see it in plants and more. This is so easy to do that it just happens all the time.
Of course, when we observe this, anti-evolutionists are quick to claim that this isn’t “really” evolution. Of course it is. In fact that is most of what we need to explain the evolution of new species.
Getting to the whole waiting time problem you raise. Our ancestors have explored billions and trillions of mutations since they diverged from chimpanzees 6 millions of years ago (try the rough calc. 6 million x 20,000 popsize x 100 mutations/gen / 15 years / gen). So we have very roughly trillion trials to tweak a few thousand gene expression and splicing signals, and there are many ways it can happen (there is not a unique solution), most of the differences we se are not even necessary (they are random drift), and sexual reproduction means they can happen in parallel (not one after the other). Remember we see this mechanism at play already on directly observable timescales.
There is more than enough time for evolution of gene expression. Remember, we see this already on an observable time scale. This is not particularly difficult.