The other thing that was unstated in the article (from which the map came from) is that there seems to be a choice of overflights to get to ICN from North America:
a. Russia and North Korea (land). Probably not allowed at any price by North Korea.
b. Russia and North Korea (sea territory). Used by the "Kamchatka Route".
c. Russia and China (land). China probably charges too much or does not let overflights at any price (note that even Hong Kong SAR based Cathay Pacific avoids overflying China land other than the Hong Kong SAR when flying from HKG to non-China destinations). Otherwise, it may be an attractive way to fly from the "Kamchatka Route" but go over China to end up west of the Korean peninsula where ICN is.
d. Japan. Used by the "North Pacific Route" which is 30-60 minutes slower than the "Kamchatka Route", according to the map.
e. Russia and Japan (sea territory). Would be a longer version of the "Kamchatka Route".
f. No overflights. Not sure if it is possible to avoid overflying any other country by flying south of Japan (since Japan controls some islands in the area and other islands in the area are disputed), but it would likely add quite a bit of flying time even if it were possible.
The last two ORD-ICN KE flights I've been on have taken the land route over Russia and China and hooked back up to ICN. Prior to that, they went down the coast of Russia to northern Japan, then turned back north to ICN. I've never been on a KE, OZ, or UA flight that went over land in North Korea. Since the DPRK navy takes shots at ROK fishing boats, it probably wouldn't be advisable.
South Korea has normalized relations with China and KE and OZ fly to several Chinese cities, so I can't imagine flying over China is a big deal. Same with Russia.
Oh, and I agree that the fees listed above must be in KRW, so divide by 1000 for a rough USD equivalent.