The only free and comprehensive online etymological dictionary of the Spanish language
gato (Noun) "cat"

10th cent. From Late Latin cattus 'id.' The voicing of Latin /k/ to Spanish /g/ is unexplained. Borrowed from an Afro-Asiatic source (compare Coptic klít "cat").

Listed by Tibón (1988) as a particularly ancient nickname for physically-gifted individuals who showed agility and reflexes like a cat; then later it fossilized into the surnames Gato, Gatón, and Gata.

Romance: Western Vulgar Latin: Asturian gatu, Portuguese gato, Galician gato, Catalan gat, French chat, Italian gatto; Eastern Vulgar Latin: Aromanian cãtushe, Romanian cătușă; Sardinian batu

The shound shift of /k/ to /g/ did not affect c-initial words in Latin, so we are left with the question of whence the g- in gato? Considering cognates in Catalan gat and Italian gatto, we could reconstruct a Vulgar Latin variant *gattus but this looks unmotivated. A loan from another language into Spanish is phonologically fine, but at odds with the historical record.