I remember when the Muslim holy book was the Koran when I was in middle school, but now it's the Quran. But it's always been Qatar and Iraq (but still Kuwait.) Who decided that 'Q' was going to be represent that sound instead of 'K', and why?
In Arabic, in fact, they've always been separate sounds! The sound we write "K" is spelled with the letter ك in Arabic, and is pronounced a little bit further forward in the mouth; the sound we write "Q" is spelled with the letter ق and pronounced a little bit farther back. In phonetic terms, "K" is a velar sound, and "Q" is a uvular sound.
English doesn't distinguish between these two different sounds. But since we've got a spare letter lying around—the English letter "Q" is actually related to the Arabic letter ق, if you go back far enough!—it's become conventional to separate them in writing. "Kuwait" is spelled with a ك, so it gets a "K"; "Qatar" is spelled with a ق, so it gets a "Q". The "Qur'an", similarly, has a ق in it.
Nowadays, by the way, the letter "Q" has started to be associated with Arabic in particular, since it shows up significantly more there than in English. So in pop culture, you'll sometimes see names like "Hakeem" respelled to "Haqim"—even though the original Arabic has a ك in it! Linguistically, this is called hypercorrection, and it's the same reason you'll see words like "forté" with an é: English-speakers associate the acute accent with Romance loans (café, fiancé, résumé), but it has no special meaning in English, so it sometimes gets inserted where it doesn't actually belong (the original Italian word is simply forte).
I was going to propose Julius Klaproth, in his 1823 book Asia Polyglotta. He notates the difference between ك and ق as k versus q. In earlier works such as Hamer 1806 Ancient alphabets both were represented as "k" with a note that [q] ق is "hard". However, I see that Christian Ravis 1649 in A discourse of the orientall tongues : viz. Ebrew, Samaritan, Calde, Syriac, Arabic, and Ethiopic together with a generall grammer for the said tongues p. 96 or 97 (in the "General grammar" part) notates the kaf / qaf distinction with k versus q as well. Subsequently, it emerged that Otho Gualtperius 1590 in Grammatica linguae sanctae described the analogous Hebrew kaph / qoph distinction as kaph c,ch (=[k,x]) versus qoph "q or k". It is worth noting that the letter "q" itself derives historically from and still resembles the Semitic letter qoph, which represented a Semitic sound that was either [q] or [k'] and is [q] in Arabic.
So at this point I would say that it is unknown who first devised that convention.
The answer to this question has multiple layers. Draconis has already noted that the two sounds are distinct (phonemic) in Arabic and user6726 has added that the convention of writing one using k and the other using q dates back quite a number of centuries. But why does the Latin alphabet even have this ‘spare letter’ (Draconis) q that turns out to be nigh perfect to write a different, k-like sound?
Much of my answer is sourced from a German video on the history of Q in the German Belles Lettres blog. Sadly, I don’t know of a translation of the entire video. But the author explores the history of why the letter Q exists in current German, why it existed in Old German and where it came from. The trivial answer to why do we have Q is that we inherited it from Latin, but why does Latin have it? Latin in turn borrowed the letter from Etruscan and initially used it somewhat unsystematically until the current convention of orthographic distinction emerged in which certain words are written with qu and most other /k/ sounds were written with c (cu contrasting with qu). Etruscan had a similar convention whereby certain vowels (u) were preceded by Q (their letter name being Koppa), others by K and others again by what the Romans would take over as C.
But why did Etruscan have three symbols for one sound? Well, all three were borrowed from one of the Ancient Greek alphabets with C actually being Greek gamma (Etruscans did not have voiced stops) and two Greek letters for the /k/ sound. However, shortly after the Etruscans borrowed the alphabet, Greek stopped using the kappa/koppa distinction altogether, most likely because there was no significant gain. The video I mentioned states that a number of /k/ sounds in Greek – that were typically spelt with koppa – migrated to /t/ sounds and others but for all intents and purposes we might just assume intelligent design and removal of clutter.
But if the Greeks had a letter Koppa that was nothing but clutter, why did they have it? Well, the Greek alphabet itself had been copied from the Phoenician alphabet. While Latin, Greek and German (and English) are Indo-European languages (and Etruscan, while not being Indo-European, has a debated origin as far as I’m aware), Phoenician is actually a Semitic language closely related to Hebrew and less closely to – you guessed it – Arabic. All these Semitic languages already had a k/q distinction (as in they had two phonemic consonants) and so it only made sense that alphabet systems (or abjad systems) designed to write these languages came up with two different letters for the two different sounds. The Phoenician alphabet is indeed among the oldest alphabets. So even if there had been some other convention to distinguish between the two Arabic k sounds in writing, it would make much more sense ‘etymologically’ to completely discard whatever else exists and use the k/q convention instead.
And why does ‘a lot of Q’ look Arabic when Hebrew has the same sound distinction? (Phoenician and most other Semitic languages are extinct and the ones that aren’t are minor, but in the western world one has a non-neglegible chance to come in contact with Hebrew names.) At some point before Hebrew as a language was revived, the k/q distinction was lost. As Hebrew became a purely liturgical language and Jews started using the native languages of the diaspora countries they were in, a lot of them no longer lived in a place that distinguished k and q phonemically so nowadays both Hebrew letters have the same pronunciation which is typically transliterated as K (Note: the Hebrew letter corresponding to K can also be pronounced as kh, which in itself is a separate orthographic and transliteration issue). This leaves Arabic as the last significant Semitic language to distinguish a k and a q sound.