Johnny Cage: Venice Beach, CA, USA
Sonya: Austin, TX, USA
Stryker: USA...possibly NYC (as he is part of NYPD)
Kai: North America...most likely USA
Jax: USA
Kano: Unknown (see paragraph below)
Sub-Zero/Tundra: USA
Sub-Zero/Noob Saibot: USA
Liu Kang: Honan Province, China
Kung Lao: China
Shang Tsung: Possibly China. It is known that he was born in Earthrealm, so he does have a nationality.
Hsu Hao: Mongolia (it is known that his beta name was Kublai Khan, a nod to the ancient ruler of that country)
Cyrax: Botswana
Smoke: Czech Republic
Now Kano's nationality should be listed under controversy. Kano's original bio officially states that he was "orphaned by an American woman in Japan". However, since 1995, Kano has carried an Australian accent, beginning with the MK movie released that same year. Since the "orphaned by an American woman in Japan" portion has never been retconned in writing, I am led to believe that the accent is a tribute to the late Trevor Goddard, who played the role of Kano in the 95 movie.