What does PAC-learnability say about the learner runtime?
PAC comes in two flavors -- "information theoretic PAC" and "efficient PAC." The latter asks for computational efficiency whereas the former cares only about sample size.  One usually understands which is referred to from context.

Indeed, it is not known whether (efficient) PAC learning is NP-hard in general, but results on the cryptographic hardness of learning as well as on hardness of proper learning make it universally believed that learning is hard.