We present a novel family of slowly rotating black hole solutions in four and higher dimensions that extend the well known Lens-Thirring spacetime and solve the field equations to linear order in rotation parameter. As "exact metrics" in their own right, the new solutions feature the following two remarkable properties: i) near the black hole horizon they can be cast in the, manifestly regular, Painlev\'e-Gullstrand form and ii) they admit exact Killing tensor symmetries. We show that such symmetries are inherited from the principal Killing--Yano tensor of the exact rotating black hole geometry in the slow rotation limit. This provides a missing link as to how the exact hidden symmetries emerge as the rotation is switched on. Remarkably, in higher dimensions the novel generalized Lens-Thirring spacetimes feature a rapidly growing number of exact irreducible Killing tensors - giving a first example of a physical spacetime with more hidden than explicit symmetries.