The tooth mouse tradition is widespread in Latin America. Raton Perez in Colombia. The story comes from Spain, Italy (Topino) and France; when or where started I don't know.

Other animals and birds (magpie) share the blame in the orient. I wonder if the camp robber (a bird) is the exchanger among some western American Indians?

The tooth fairy seems to be a fairly recent invention, ca. 1890s, from what I have found so far.