To make matters worse, since some times protein coding genes evolve de novo from non-coding DNA, new functional proteins can actually emerge without the feedback of selection gradually producing them. As mutations accumulate in the DNA, promoters can emerge and yield expression of downstream sequences containing valid open reading frames, which can by chance alone turn out to have useful biological functions. From there on selection can fine tune the function.
There’s simply no reason to think the total size of sequences space is any kind of obstacle to the evolutionary diversification of life.