The palatalization of the Vulgar Latin sound /k/ into Modern Romance /s/, /ʃ/, and /tʃ/ is a well-established fact (as in centum > cent, cantare > chanter in French, and centum > cento in Italian). However, the way this sound change occurred seems to have escaped much attention.
According to the generally accepted view, the softened /kʲ/ turned into /tʲ/ through a certain shift of the point of articulation, followed by a transformation into /ts/ and eventually /s/ in Modern French. (See, for example, Elcock The Romance languages, p. 53.)
Since a sound change is rarely a sudden switch to a completely different sound, there should be a clear transformation chain, where each pair of the neighboring sounds are close allophones that can be unquestionably taken for a single phoneme by speakers of the language. Taking this into account and looking at the aforementioned sound chain: /k/ > /kʲ/ > /tʲ/ > /ts/ > /s/, it is hard to figure out how speakers of the language could treat /kʲ/ and /tʲ/ as close variations of the same sound, while speaking to each other.
On the other hand, a live example of a phonetical variation in Modern German seems to suggest a different perspective. The sound pronounced as /ç/ in Standard German (as in ich) is rendered as /k/ and /kʲ/ in Low German, /ɕ/ and /j/ in Central Franconian including Kölsch. Not only does it provide a detailed insight to the possible transformations of the /k/ sound, but it is also entirely credible, since it is still observed in the living language varieties. The sheer existence of such a variation in a geographically neighboring language is certainly not an ultimate proof, but it does provide a clear hint.
The Vulgar Latin /k/ > Modern French /ʃ/ sound change could have passed in the following steps:
/k/ > /kʲ/ > /ç/ > /ɕ/ > /ʃ/, as in cantare > chanter
In this chain, each pair of the neighboring sounds are close allophones that could be taken for a single phoneme by speakers of the language, as proven by modern Germans. The other possibilities of the development of Vulgar Latin /k/ observable in Modern French can also be aligned with this chain:
/k/ > /kʲ/ > /ç/ > /ɕ/ > /sʲ/ > /s/, as in centum > cent
/k/ > /kʲ/ > /ç/ > /j/ > /∅/, as in facere > faire
A similar transformation — and probably the source for its counterpart in Vulgar Latin — emerged in Greek. The sound represented by the letter χ shifted from /kʰ/ in Ancient Greek to /x/ or /ç/ in Modern Greek. Numerous Latin borrowings from Greek (like schola) and the overall influence of the latter could contribute to the coherence of certain phonetical patterns in the two languages.
(1) These chains can also be slightly adjusted to fit Modern Italian:
/k/ > /k/, unchanged as in cantare
/k/ > /kʲ/ > /ç/ > /ɕ/ > /tɕ/ > /tʃ/, as in centum > cento
(2) Similarly, a /tɕ/ or /tʃ/ sound could have emerged from /ɕ/ in varieties of Old French, not as a predecessor of /ʃ/, but as an alternative. This particular variant could have been borrowed into English (to be nowadays observed in English loanwords like chair).
(3) Since the sound change /k/ > /ts/ does occur in other languages, it still seems reasonable to assume that in these languages /ts/ is a further development of /tɕ/ in the same sound chain.