I'm not a native speaker of English, but my guess is that it's because "Southern Europe" is an "official" region, while in "northern Norway" you are speaking about a part of a country. We do something similar in Brazil: the country is officialy divided in five regions, so if you say "South Brazil", you are speaking about those three states that are considered in this region by our Institute of Geography, while writing "south Bahia" requires no capital S in "south" because you are not speaking of a "proper noun", just stating the specific cardinal direction. :)
As far as I undertsand it, storio is correct... because Southern Europe is a pretty well defined region commonly reffered to it becomes almost a name of its own, whereas with northern Norway you are simply specifying the specific part of a region or country or area; northern is used as an adjective to the noun rather than part of the noun itself.
Hope I could help :)
karta is a loan word from Latin 'charta', 'papyrus' or 'paper'.
In English, 'map' comes from another Latin word, 'mappa', meaning 'sheet' or 'napkin'. (via the word 'mappa mundi' meaning 'sheet of the world' i.e. 'map of the world').
The word 'cartography' has the same etymology ('charta'), only it's come via French, which is why it has a c instead of ch.