The Latin alphabet is based on the Etruscan alphabet, which had three signs for the /k/ sound: C (𐌂), K (𐌊), and Q (𐌒). The reason for that is that the Western Greek alphabet the Etruscan alphabet was based on used C for /g/ (i.e. Γ), which is a sound Etruscan did not have, and already had two signs for /k/, K (Κ) and Q (Ϙ). The reason the Western Greek alphabet had both K and Q is because in the Phoenician alphabet it was based on these signs (kaph 𐤊 and qoph 𐤒) represented separate sounds, with kaph being a regular /k/ and qoph originally being the emphatic equivalent, which later became the voiceless uvular plosive /q/.
||C /k/, /g/
||Q /k/ (but see below)
None of these distinctions were phonemic in Etruscan (Latin did have /g/, so it later needed to innovate the G sign by adding a horizontal line to C; initially it used C for both /k/ and /g/), but phonetically /k/ was perhaps realised as [q] before rounded vowels (just o in Etruscan; in Latin also u) and consonantal u, so it used Q in those positions, and early Latin inscriptions mostly copied that. K was used before /a/, and C elsewhere.
Later, spelling fashions changed as people realised they really didn't need three signs for one phoneme and C began to be used pretty much everywhere except before consonantal u, where Q was kept. The reason Q was kept there is because the velar in qu actually isn't the phoneme /k/ in Latin; actually, rather than the consonant cluster /kw/, qu represents a single phoneme /kʷ/. We know this from e.g. poetic scansion, where a short vowel followed by qu doesn't become heavy by position as it would if it were followed by two consonants.
It probably would have made more sense to start writing /kʷ/ as just q instead of qu, /g/ as C, and use K for everything else (Arma virumqe kano, Troiae qi primus ab oris &c.), but historical baggage is hard to shed.
(Latin using digraphs to represent sounds that are awkward fits in the Etruscan alphabet has precedent: the Praeneste fibula famously writes Old Latin fefaked as FHEFHAKED, and this is because Etruscan 𐌅 actually represents /w/, not /f/; Etruscan doesn't have /f/.)