Are there any learning algorithms with any provable guarantees for manifold learning or manifold regularization?
It depends what you mean by "learn[ing] the manifold", but here are a few papers that present some algorithms and a theoretical analysis:


Isomap (see tech report by Bernstein, de Silva, Langford and Tenenbaum)
Random linear projections (see paper by Ken Clarkson)
Nash-type embedding (see paper by Nakul Verma)
Maximum variance unfolding (see arXiv:1209.0016)


In terms of using/exploiting manifold structure to help learning or estimation, there are many such results. For example, many of the papers by Misha Belkin and Samory Kpotufe explore this direction.