Kitaev's honeycomb-lattice compass model describes a spin liquid with emergent fractionalized excitations. Here, we study the physics of isolated magnetic impurities coupled to the Kitaev spin-liquid host. We reformulate this Kondo-type problem in terms of a many-state quantum impurity coupled to a multichannel bath of Majorana fermions and present the numerically exact solution using Wilson's numerical renormalization group technique. Quantum phase transitions occur as a function of Kondo coupling and locally applied field. At zero field, the impurity moment is partially screened only when it binds an emergent gauge flux, while otherwise it becomes free at low temperatures. We show how Majorana degrees of freedom determine the fixed-point properties, make contact with Kondo screening in pseudogap Fermi systems, and discuss effects away from the dilute limit.