Lots of Vishnu avatars have repeated during the previous Chaturyugas.
Are there any references citing the Kalki avatar in previous Yugas?
First of all, we know for a fact that Kalki doesn't come in every Kali Yuga. In this chapter of the Matsya Purana (an important Hindu scripture), various incarnations of Vishnu in the present Vaivasvata Manvantara are listed, but Kalki is only mentioned once, in the current Kali Yuga. This excerpt from the Skanda Purana says the same thing. (See my questions here, here, and here relating to these lists.)
And we can find explicit references to how Kali Yugas have ended in the past. In particular, this chapter of the Drona Parva of the Mahabharata describes how Vishnu's incarnation Parashurama brought about the end of the 19th Kali Yuga of the Vaivasvata Manvantara by killing the kings of the world:
Even the great ascetic Rama, the hero worshipped by all heroes, that son of Jamadagni, of great fame, will die, without being contented (with the period of his life). Rooting out all evils from the earth, he caused the primeval Yuga to set in. Having obtained unrivalled prosperity, no fault could be seen in him. His father having been slain and his calf having been stolen by the Kshatriyas, he without any boast, slew Kartavirya who had never been vanquished before by foes. With his bow he slew four and sixty times ten thousand Kshatriyas already within the jaws of death. In that slaughter were included fourteen thousand Brahmana-hating Kshatriyas of the Dantakura country, all of whom he slew. Of the Haihayas, he slew a thousand with his short club, a thousand with his sword, and a thousand by hanging. Heroic warriors, with their cars, steeds, and elephants, lay dead on the field, slain by the wise son of Jamadagni, enraged at the slaughter of his father. And Rama, on that occasion, slew ten thousand Kshatriyas with his axe.
But as I discuss in this answer, Vishnu did take one earlier Kalki-like incarnation in the Swayambhuva Manvantara. His name was Pramati (as opposed to the present Kalki who will be named Vishnu Yasha), and his story is described in this excerpt from the Matsya Purana:
King Pramati of the Bhrigu family and Chandramasa gotra was born at the end of Swayambhuva Manu in the Sandhyamsha period, to inflict proper punishment on the sinners. That king travelled all over the earth for 30 years and collected arms and ammunitions, elephants, horses and chariots and marched with a vast army consisting of horses and elephants and accompanied by 100,000 Brahmana soldiers armed with various kinds of weapons, against the Mlecchas and destroyed them. After killing all the Sudra kings he annihilated all the hypocrites After destroying all the sinners and subduing the people living in the North, central regions, the mountaineers, the inhabitants in the East and West, the residents on the Vindhyas, the Deccanis, the Dravidians, the Singhalese, the inhabitants of the Mleccha countnes...
King Pramati was born of Vishnu's part in Manu's family and was famous as Chandramasa. He roamed about the Earth for 20 years and killed all the wicked men in his 32nd year.