Since a sound change is rarely a sudden switch to a completely different sound, there should be a clear sound transformation chain, where each pair of the neighboring sounds are close allophones which 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 the same phoneme, while speaking to each other.
On the other hand, there is a live example of a very similar—in terms of the final output—phonetical variation in Modern German. 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. This chain is also pretty consistent with the other possibilities of the development of Vulgar Latin /k/ observable in Modern French:
/k/ > /kʲ/ > /ç/ > /ɕ/ > /sʲ/ > /s/, as in centum > cent
/k/ > /kʲ/ > /ç/ > /j/ > /∅/, as in facere > faire
Related phonetical changes1. 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 stick to the same sound chain in these languages and assume that /ts/ is a further development of /tɕ/.