The palatalisation of Mandarin velars (and other Chinese languages) is well-documented, akin to the Great Vowel Shift in English. For a paper discussing just one piece of the evidence, see this, on an eighteenth century Manchu–Mandarin phrasebook:
For most of the period of contact with Europeans, Nanjing Mandarin was the prestige version. Nanjing Mandarin underwent the palatalisation process later than northern Mandarin, as reflected in the phonetic research of missionaries, and the transfer of words into surrounding languages. For older examples of k versus j, think about how words from Tang-era China were adopted into Japanese. The same 京 that we're discussing here became "kyō". The Japanese didn't change all the j sounds to k sounds. They kept the k sounds from the source language, and then Chinese changed after the borrowing had taken place.
Cute, but not borne out by the historical/phonetic record. Peking (or Pekin) was written thus for at least a couple of centuries before Mr Wade first put pen to paper. Also, saying that Wade–Giles Beijing was "originally" Peiching implies that this later changed. It didn't. In WG Beijing has always been written Peiching. Ditto for Keelung, which was always Chilung in WG.
If you want a lot more on the origins of Peking/Beijing, then try this paper (though I'm not sure I buy the conclusions about Sino–PIE relations between some phonemes).
Edit to add: "Palatalization of the Velars" sounds like a Star Wars prequel that never got made.