If you look at the qualifier Quintilian adds (the video translates it as "the letter C keeps its strength before all the vowels"), you can see why K was in use at the time -- the sound change familiar from modern Romance languages, where C "softens" to [s] or [tʃ] before front vowels, made indicating [k] before front vowels difficult.

That is an innovation to deal with language change. It is not a part of classical or old Latin. Quintilian isn't proposing dropping K because C makes it unnecessary; he's proposing retroactively not adopting K in the first place because the change that prompted people to use it is wrong.