The flaw in his argument, from what I can see in your quotes, is to equate evolution to natural selection. Natural selection was never proposed to explain all evolution, nor how advantageous traits arise, but was proposed to explain how advantageous traits spread. Ultimately, why adaptation is so prevalent?
The modern theory of evolution is so much more than a theory of evolution by natural selection. It can explain perfectly well how all variation has come in to being. Its mechanisms of mutation, migration, drift, and selection can both erode and generate new genetic variation. New genetic variation, and the phenotypic changes that brings, occurs by mutation. Various types of mutation can occur.
Mutations are random in their effect. Now it is possible that mutation rates are not random; if you imagine two theoretical species which have both gone through genetic bottlenecks, such that they both have little genetic variation, then the species with a higher mutation rate might have a better chance of staving off extinction because mutation will increase genetic variation, and genetic variation limits the rate of adaptation. Therefore, if there is a genetically coded trait which increases mutation rates then it may spread. Conversely, mutation is generally detrimental (see Fisher's Geometric Model) so, in general, there will also be selection for lower rates of mutation. From what I can gather on Wagner's theory on innovation is that mutation may be some kind of premeditated, directed mechanism with the organism trying to make a certain trait evolve. This is generally considered to be highly unlikely within the evolutionary biology community and, as far as I am aware, there is no evidence of it occurring.
Related posts I've made on biology SE:
Having read some more on his theory, I think I am more clear on what he means. He uses the term innovation as other evolutionary biologists would use adaptation. I've no idea why he does this, there's no need to be using divergent terminology. Ultimately he is proposing adaptation by natural selection.
"Very occasionally, one or more mutations may also bring forth evolutionary innovations—new phenotypes that are qualitatively different and superior to the existing phenotypes."
"Evolutionary innovations can be difficult to define rigorously [1,2], but they are often easy to recognize as qualitatively new and adaptive traits of organisms. In addition, they also frequently provide new platforms upon which further evolutionary change can unfold."
The problem with this comes because he uses his own preconception that time simply has not been sufficient to allow all of the genetic variation to arise, to insinuate that random mutation is insufficient.
"Random change by itself is not sufficient, because it does not necessarily bring forth beneficial phenotypes."
The writing is suggestive (strong emphasis on suggestive, he never states this as far I can tell but the writing lends itself to misconception) that he will invoke some kind of directed mutation argument. However, his actual idea seems to be that genes interact and therefore this will increase the rate at which mutations cause phenotypic change. Because there is temporal and spatial variation not just in genetic variation, but also in selection, neutral mutations may accumulate in genes which later have an effect on fitness (either by interacting with new mutations elsewhere in the genetic network, or by shifts in the adaptive landscape).
"Wagner has emphasized how epistasis – interactions among genes that shape the adaptive consequences of mutations – allows neutral variation to modulate the effects of other mutations, producing a vast range of possible mutant phenotypes that may lead to an adaptive innovation."
This is nothing particularly new or controversial (see epistasis, gene networks, and read on evolution from standing vs. novel genetic variation). Basically, Wagner appears to suggest that Darwin's theory relies on novel mutation arriving after selection changes, which it does not, and Wagner's theory is simply a way for standing genetic variation to persist through gene networks. I don't think the concept of standing genetic variation is novel here, but the possibility that standing genetic variation may come under selection because of further mutation elsewhere in the gene network does appear to be novelty of his work.
MattDMo makes an excellent point on Wagner's assertion that all mutations occurring at random over just 3.8b years is implausible:
This is an argument from incredulity, a logical fallacy. Just because you can't imagine something happening, doesn't mean it can't happen.
Can random mutations over a mere 3.8 billion years really be responsible for wings [...]?This is an argument from incredulity, a logical fallacy. Just because you can't imagine something happening, doesn't mean it can't happen. $\endgroup$