I disagree. The search space is going to be dependent on the pre-existing genome, and we simply don’t know enough about genomes 400 million years ago to do this, at least from what I can see. You seem to be assuming that functional sequences emerge de novo from previously non-functional DNA, but this certainly doesn’t have to be the case. There could have been pre-cursor genes that had functional tertiary structures that were then modified through subsequent mutations. That pre-cursor gene could have been lost to history. If there is billions of years of evolution that led to a gene that was one mutation away from finding a novel function, then you would need to factor in those billions of years of evolution into your calculations.
Those approximations are wild guesses, at best. On top of that, your target space needs to incorporate all functional space, not just the function that did evolve. Nature is full of species that found different strategies for adapting to environmental challenges, and I would suggest this extends to the molecular level. For example, intron splicing is just one possible function that could have arisen. A completely different method for dealing with misfolded proteins could have emerged.