Heian was actually "Heian-kyō" -- "Tranquility and peace capital". Kyōto means essentially "Imperial capital city" -- the "Kyō" in both terms is the same character (京); this is used for "capital" in other Asian languages that use Chinese characters. Beijing, for example, is 北京, "Northern capital", similarly Tōkyō is 東京 or "Eastern Capital"

So Heian-kyo and Kyoto aren't really that different as names, it's more that they're different stylings of the same idea -- you might compare to the minimal distinction between "Washington DC" and "The District of Columbia"; or perhaps "DC" vs "Capital District". One of them might become preferred by usage, without anyone ever saying "we're changing the name of the city".

The change is associated with the end of the Heian era and the victory of Minamoto no Yoritomo in the Genpei War, but it's a gradual process, not a deliberate name change. There isn't any formal renaming of the city or explanation-- it's just an alternative usage that becomes more common.

The change seems to occur by the 12th century, with the eclipse of Fujiwara, the Taira rebellion, and the rise of the bakufu-- the military government of the Kamakura shoguns. I've heard some suggest that "Heian-kyō" was insufficiently strong as a term for the new military rulers. . . this is a time of almost constant warfare, including around the capital; perhaps the irony got to them. But I'd also observe that Japan is filled with changing names. Many important historical figures have several by which they are known. Similarly Tokyo was previously known as Edo.

Kyoto actually briefly has a third name, when the capital is moved to the (renamed Edo) Tokyo in the Meiji period-- it's suggested that that Kyoto be called the "Western Capital" = "Saikyo", but I don't know that anyone ever used that name much.