We study the virtual geometry of the moduli spaces of curves and sheaves on K3 surfaces in primitive classes. Equivalences relating the reduced Gromov-Witten invariants of K3 surfaces to characteristic numbers of stable pairs moduli spaces are proven. As a consequence, we prove the Katz-Klemm-Vafa conjecture evaluating $\lambda_g$ integrals (in all genera) in terms of explicit modular forms. Indeed, all K3 invariants in primitive classes are shown to be governed by modular forms. The method of proof is by degeneration to elliptically fibered rational surfaces. New formulas relating reduced virtual classes on K3 surfaces to standard virtual classes after degeneration are needed for both maps and sheaves. We also prove a Gromov-Witten/Pairs correspondence for toric 3-folds. Our approach uses a result of Kiem and Li to produce reduced classes. In Appendix A, we answer a number of questions about the relationship between the Kiem-Li approach, traditional virtual cycles, and symmetric obstruction theories. The interplay between the boundary geometry of the moduli spaces of curves, K3 surfaces, and modular forms is explored in Appendix B by A. Pixton.