Is the ultimate challenge in ML simply computational power?
There is something known as the VC dimension of a hypothesis class. This refers to the maximum number of datapoints with arbitrary binary labels that can be correctly classified by a model from the hypothesis class. 

https://en.wikipedia.org/wiki/VC_dimension

If your number of datapoints is larger than the VC dimension for the hypothesis class you have chosen (say set of 2d hyperplanes), then no matter how much you tune your model using cross validation you can never achieve complete accuracy. Hence, the analyst has the important job of choosing the correct hypothesis class while making sure it doesn't overfit. In the case of deep learning this would mean coming up with a specific architecture and is often one of the most difficult tasks.