There is no one, easy answer for where each region (or country) got their one- or two-letter designation. Many of them evolved over time. When the ICAO (as an organizational body) was formed out of the international conference in Chicago in November 1944, dozens (or hundreds?) of things needed to be standardized between nations. One of these things was a standard way to identify airports. (Another was aircraft registrations... a minor, but related, blurb about that at the end.)
Many of these attending countries already had a "standardized letter prefix" from the 1912 convention in London regarding telecommunication call signs. For example, Canada was C (easy to understand why), and the United States was either W or K (less easy to see why, but there is history there, too -- see below). Other countries who were members to the 1912 convention had various call signs, some of which started with numbers. These countries, obviously, did not easily convert over to a letter prefix system that ICAO was adopting. At the end of the day, there were numerous ICAO committee meetings (and I can only imagine some heated arguments between delegates) that eventually resulted in the various regions and sub-regions we know today and that are depicted on the map below.
A small bit of history on how the USA evolved to the letter K: In the late 1800s, when telegraph was getting under way and Morse Code was in heavy use, there were two very easy to use Morse Code letters: A (dot dash) and N (dash dot). The US Government reserved these two letters for its military telegraph station call signs, and assigned A to the Army and N to the Navy. Makes some logical sense so far. Of course, the civilians were wanting to get in on the revolutionary breakthrough of wired (and eventually wireless) telegraphic communications, so the US Government created a civilian set of call signs in addition to the military ones. To do this, they simply added a single dash to each Morse Code letter, and the dot-dash (A) became dot-dash-dash (W) and the dash-dot (N) became dash-dot-dash (K).
The USA now essentially had four different letter-prefix designations for its radio station call signs: A and N (military use), and W and K (civilian use). The W and K call signs were also geographically separated with K being assigned to all stations in the west, and W for all stations to the east. The "border" between K and W changed over time, eventually landing on the Mississippi river, but that's another topic. You still see this today in your AM/FM music broadcasting and TV stations, with most stations "out west" being a Kxxx identifier.
Eventually, voice radios became very popular, and all new stations were only issued the letter K. W-stations were grandfathered in. Additionally, radio stations began to be carried onboard aircraft, and the previous military-only letter of N was eventually assigned to all airborne radios, including civilian. Aircraft began marking their exteriors with their N-xxx radio call sign.
Anyway, to make a long story short (too late?), the US was able to exert is muscle at the 1912 conference in London, and all 4 of those letter prefixes (A, N, W, and K) were retained for sole use to the US. But 35 years later, during the formation of the ICAO and the resulting subcommittees, the US agreed to be "Letter K" for its airport designations and "Letter N" for its aircraft registrations, losing the letters W and A (at least in the ICAO books). Also, remember that Alaska and Hawaii were not yet states, so they were both lumped into the Pacific Region [P] with sub-regional designations of PH and PA, along with all the other Pacific Region subs (PG for Guam, PM for Midway, PB for Baker, etc.).
