What was the significance of Leslie Valiant's, "A Theory of the Learnable?" It seems like two of the main takeaways were that there is a natural limit to what computers can learn, and learning is bounded by polynomial algorithms. Why was his paper significant in the broader area of machine learning?
I think that "there is a natural limit to what computers can learn", while definitely true, is not one of the main takeaways of Valiant's paper, for two reasons. One is that I could not find any discussion of lower bounds or no-free-lunch results in this paper. Two is that surely statisticians had been aware of such fundamental limitations on learnability prior to Valiant, if only as folklore.

I'd say the reason that paper has had such an impact is that it formalized an intuitively appealing learning model (what came to be known as PAC), which turned out to have a rich and satisfying mathematical structure, as well as numerous generalizations and extensions. Of course, finite-sample bounds had been obtained by Vapnik and Chervonenkis previously, but Valiant placed learning in an algorithmic setting by (among other things) emphasizing the importance of representation. In particular, he argued that DNFs are a natural human-interpretable representation and wondered whether these can be efficiently PAC-learned. (We now know that properly PAC-learning 3-term DNFs in polytime would imply NP=RP, but the agnostic case is still an active area of research and a major open question, as far as I know).

In summary: by Valiant's own admission, the statistical contributions of the paper are minor. He doesn't even need the full power of VC theory, since he mostly (exclusively) deals with discrete function classes, for which cardinality bounds + Chernoff do just fine. The reason that this paper has had such an impact on CS -- and indeed, probably the main reason why machine learning, by default, resides in CS departments -- has mainly to do with the computational aspects.