It's probably both. I doubt wild ones are just *given* keys, for instance.Since the keys are just given to Klefki I don't think its name comes from kleptomaniac. It seems more likely that it comes from clef, the French for key.
Incidentally this makes its floating around and unlocking things for you Keykey's Delivery Service.