Hcfyk

You will likely have an easier time if you pick a Slavic language that uses a Roman alphabet. Like Czech or Slovak (which are very similar to each other). Then you don't have to deal with the unknown alphabet and words that are more removed from Latin/etc.

Take Slovakia. It's got some pretty straight-forward place name conventions. I do a lot of genealogy work in Slovakia (don't speak the language though). My favorite resource is a list of every single village and town and city in the entire country. It gives current and historical names. I rely on it extensively when I do records transcriptions.

Do keep in mind that, over the years, places in Slovakia have had not only Slovak names but also names from the languages of other countries that either controlled (all or part of) the country or supplied a lot of migrants to it or had influence due to the Church, etc. Hungarian is the biggest. But also Russian and German (and Latin and Polish and...).

There are many rivers in Slovakia and it is common to have towns named after a nearby river. So some of your towns will likely be named after waterways on your planet.

Many towns are also named as by the river. For example:

• Nové Mesto nad Váhom


• Dubnica nad Váhom

Are both on the Váh River (Slovakia's largest river, a tributary to the Danube).

• Vyškovce nad Ipľom


• Veľká nad Ipľom

Are on the Ipeľ River.

A great resource for Common Place-Name Terminology lists place names in Hungarian, Slovak, Polish, German, and English.

For example, big town by the Little River would be:

Velke Mestro nad Kisom

Start with some basic translations for words that create town names in English: Valley, Vista, Hills, Lake, Flats, Ville, Oaks, Port, Plains, Junction, City, Town, Land, Harbor, etc.

Throw in color names.

Instead of Oaks, use the plant and animal life you will find there. Violet Flats or Pine Hills.

Use the first and/or last names of the people who first arrived in that region. Or their professions. Friersland or Captainsport.

Use the names of the prominent industry in the town. As in Bakersville or Tanners Lake.

Now divide similar areas by adding words for big, little, and so on. Lower Redwood vs Upper Redwood.

And use the various naming conventions to add some flair. Speckled Rooster by the Smith River.

And translate it into your favorite Slavic language (if for some reason it's not Slovak).

I believe you have two options here

1) make up something generally Slavic sounding

2) get a native speaker to help you out. As a Czech I see way to much weirdness already in the suggestions here on this page only (e.g. Novyruska or Novyruskia absolutely cannot work, Russia is feminine and novy is masculine, you need nová/novaya/depends on specific language, but definitely not novy)

Lift them from real places.

Here is a map of medieval Kievan Rus from Wikipedia.

https://upload.wikimedia.org/wikipedia/commons/d/db/Principalities_of_Kievan_Rus%27_%281054-1132%29.jpg

Good names: Halych, Kiev, Volyn, Smolensk, Polotsk. Also "Chud", which was a surprise to me. You could get names like this off of other maps of Slavic areas.

Now mangle them a little bit to account for the years and drift and ignorance. You could add, or alter. Or drop a vowel: Hlych, Kiv, Vlyn, Smlensk, Plotsk. Still slavic sounding but not in your face obvious liftings.

Chud really has nowhere to go with that method and probably is good as is.

As Cyn already suggested, many names are related to the river it is close to. You can use the list below to sythesize your own names and then let them checked to avoid names that just sound slavic but does not make any sense in any slavic language. Something like "Your eyes September" ->(cz) Tvoje oči Září -> "Your eyes shine."

The cities here got their names, or part of their names, from:

• The founder, she saint or the significant person.
  Karlovy Vary after Charles IV. (Karel IV), Stalingrad after Jossip Vissarionovich Dzugashvili, the Soviet dictator, Gottwaldov after Klement Gottwald (Czechoslovak Stalin), Jindřichův Hradec - Jindřich, a member of Rožmberk house found the fortress and took the name Jindřich z Hradce as the name of his own house (páni z Hradce - lords of Hradec). Havlíčkův Brod - after a poet, writer and newspaper editor Karel Havlíček Borovský, Svatý Jan pod Skalou - st. John, Other examples: Pennsylvania, Monte Carlo


• The coat of arms of the land owner.
  Rožmberk - Rosenberg (The coat of arms cosists of a red rose on silver shield)


• After the fort, castle, monatstery, church it was build close to.
  
  Jindřichův Hradec - fort or small castle, Kostelec nad Černými lesy - Church, Klášterec nad Ohří - monastery, Stalingrad - a castle. Other examples: Graz, Nürnberg, Fort William, Newcastle upon Tyne


• How the place for settlement was obtained.
  Žďár nad Sázavou - žďářit = to burn the forrest to free the land for settlement or fields. Červená Lhota - Lhota was a period of time the new inhabitants were free of taxes and duties to the land owner. Dvůr Králové - The city was a queen's property.


• After a feature nearby.
  
  Karlovy Vary - a hot springs, Mariánské Lázně - a spa, Kostelec nad Černými lesy - is is located on the hill and used to be surrounded by dark forrests (černé lesy), Karlštejn - stein (german) -> stone, based on rocky terrain, Rožmberk - berg (german) -> a hill, Kutná Hora - kutat = to mine (Kutná Hora was the most significant silver minig city), Blato - swamps, Nová Bystřice - springs, Havlíčkův Brod - a ford through river Sázava, Other examples: Palm Springs


• Major settlement nearby.
  
  Kostelec u Jihlavy - Jihlava (Iglau) was the major silver-minig city in the region, Úvaly u Prahy - Praha (Prag, Prague)


• To distinguish the location or age of two settlements.
  Nové Město na Moravě - new, Stará Boleslav - old, Mladá Boleslav - young, Horní Jiřetín - above the other, Dolní Věstonice - below the other. Horní Malá Úpa - small. Other Examples: New York, Obersdorf


• To determine the status of the settlement.
  
  Nové Město na Moravě - holds the rights of a city, Ves Touškov - a village, Městec Králové - larger than village and holds some rights of a city, Dvůr Králové - hof (german), a major agricultural centre owned directly by a member of a house or king. Other examples: Salt Lake City, Georgetown


• Geographical desctiption.
  
  Klášterec nad Ohří - a settlement on the river of Ohře, Mníšek pod Brdy - settlement based under the Brdy mountains, Kutná Hora - a mountain. Other examples: Salt Lake City, Kingston upon Thames


• Major resources gathered nearby.
  Stříbro - silver, Železné Hory - iron,


• Some word.
  
  Kokotsko - kokot = rooster, Buková - buk = beech,...

How to make Slavic names?

Take the thing as it is. For example a mountain that is black slopes or is overgrown with dark forest, almost black. Call it just that "Black mountain". Černá Hora in Czech or Crna Gora in Montenegrin. Swap G for H and as you wish. Mash words together. So a "New City" translated to Slavic would be Novi Grad, after two changes it's Novyhrad.
Then you name things from the feelings. There is a city named after "I'm happy" Cieszyn

Third thing is if you want to make English sounding names but with a sign of being made by Slavs. Then you can easily add -ski/-sky at the end. For example "Smithski" (that would be used when a place would be named after person or after some profession Admiralski)

Fourth would be adding -rsk to the end. On Moon you have a Mare Humorum. If Slavs would make a settlement there it could be called "Novo" (from new) Humorum (from earlier place) and add rks. Novohumorumsk

Talking of Russian: I think they adapted Game of thrones locations just brilliantly. Like there is a spot "Black Waters", straightforward translation of which would be "Chornyie Vody" or singular "Chornaya Voda", which might be more readable for you. But they've chosen "Chernovodnaya". A single word! Furthermore, it's an adjective, not a noun. Very authentic though.
Just don't experiment this way with "Novaya Rossiya" you mentioned somewhere in discussion. "Novorossiya" will be very politically sensitive these days.
And there are many other examples is you check the map in Russian. Like the place called "Fingers" will be translated by Google like "Paltsy", but you will see "Persty" instead, which is an old word seldom used nowadays. Still more beautiful as for location name I believe.

To get a specific help, you need provide a more detailed description of the place. Otherwise you will get nothing better than "New (Russia, land, Earth, country, planet...)". The name can refer to: geographical location (like Oriental Pearl), geology (Sands), flora (Bamboo Forest), fauna (Eagle's Nest), feelings (Cape of Good Hope) or even the person, who discovered it (America itself).
So, give me what you have or what you want and maybe I'll come up with something decent.

If you look to the New World, geographic names in new settlements are usually quite uninventive.

Apart from names inherited from the original inhabitants, the colonists tended to name their settlements the same thing as their place of origin (Paris, Texas), optionally adding "New" in front of it (New York, New Amsterdam, Nova Scotia), the same which also occurred when Russia expanded eastward (Novaja Zemlja, Novosibirsk).

As you pointed out with regard to Pennsylvania (and the same goes for Georgia, Georgetown or Louisiana), the name of a leader or conqueror is also often used.

Other geographical names in the New World tend to be plainly descriptive (Rocky Mountains, Mexico City, Minas Gerais = Public Mines) or named after the occasion on which they were discovered or conquered (Rio de Janeiro = January River, São Paulo = St. Paul because it was founded on the day of the conversion of Paul). Even Brazil itself is named after its primary export – a kind of wood.

So just by using a map of Slavic Europe, a calendar, the word "new" and a simple glossary you can name an entire continent quite easily.

This is to support the answer by idrougge: "geographic names in new settlements are usually quite uninventive." I live in Australia, which was settled mostly by people from Britain. Of course, in Australia there were already Aboriginal people, and quite a few place names derive from local Aboriginal languages (often as mis-heard by British settlers). I don't know if your scenario includes pre-existing language-using inhabitants: if so there is another source of names, which can look completely different from the Slavic-derived names.

If I just look at non-Aboriginal names, a lot of them are names of people, often politicians in power in Britain at the time (Melbourne after Viscount Melbourne, Sydney after Viscount Sydney), or prominent early leaders in Australia (Governor Macquarie gave his name to several things, including the Macquarie River). The suburb of Collingwood in Melbourne was named after either Baron Collingwood (a famous British admiral) or after the Collingwood Hotel (which was named after Baron Collingwood and was an early building in the area).

The rivers aren't generally named after British rivers. The Darling River was named after the then Governor of New South Wales, who instigated an exploratory expedition. The Murray River was named after a British politician. The Murray and the Darling are the two biggest rivers in Australia. The Diamantina River was named after the wife of the first Governor of Queensland. The Swan River in Western Australia was the first place that black swans were seen by Europeans.

Another big category (probably the biggest) is names of somewhere in Britain, such as Ascot, Richmond, Perth, Newcastle, the Grampian Mountains, Pentridge (which was the name of a notorious jail in Melbourne, but is an English place name). Very few of these have "New" in their names; they just took the British name unaltered. The State of New South Wales is an exception. New Norcia was established by Spanish Benedictines, and named after Norcia in Italy where St Benedict was born. The town of Clunes acquired its name from a local farming property called "Clunes"; the name is originally Scottish. The suburb of Coburg was named to commemorate the visit of the then Duke of Edinburgh, who was a member of the royal house of Saxe-Coburg and Gotha. Bacchus Marsh was named after an early settler, an Englishman called Captain Bacchus. Vaucluse was named after the first homestead in the area, Vaucluse House, which was in turn named after a poem by the 14th century Italian poet Petrarch. The suburb of Wyoming was named after a once popular ballad, written when Wyoming in the U.S.A. was a Territory (not yet a State). Note that not all the names are ultimately British (though most are); the British absorbed influences from other cultures, as did the Slavs.

Names that arose locally: Bald Hills, Poverty Point, the Snowy Mountains, Mount Disappointment, Mount Misery and Mount Hopeless (in three different Australian States), Diggers Rest and Miners Rest, Airport West (it is a suburb). There is a locality called Dead Horse Gap in the Snowy Mountains, but I don't think anyone lives there. Kangaroo Valley and Emu Plains are named after native fauna. Chatswood was named after Charlotte Harnett, wife of a pioneer in the area, and was originally called "Chattie's Wood", "Chattie" being Charlotte's nickname, and the area being forested then (now it is a very dense urban area).

The gold rush in Australia gave rise to various names such as Golden Square and Canadian Lead. The town of Research (originally Swiper's Gully, then Research Gully) was so named because after the gold rush started the area was re-searched (searched again), and gold was found. Poverty Point was renamed Golden Point when gold was found there. I think the Radio Springs Hotel was named after radioactive springs in the area, which were considered to be therapeutic.

Some names are just inexplicable, such as the Sydney suburb of Dee Why.

Why have your Slavic people settled this planet, and have they been there a long time? What is the history of the settlement? Who sent them originally? Were they convicts or prisoners, were they fleeing oppression, or were they just trying to make better lives for themselves? Was the beginning of the settlement really difficult? Are there strange flora or fauna? Did the first settlers carve out large estates, naming them however they felt like, which afterwards gave their names to towns? Was there something like a gold rush or other significant event?

Maybe Australian names will give you useful parallels.

What is a Slavic name? Is, for example, Sankt Peterburg a Slavic name? After all, it's a very large city in Russia and it used to be capital city of the Russian Empire. But the name is actually made of one Latin, one Greek and one Germanic component; the more Slavic equivalent is Petrograd (still has a Greek component, but Petr it's more Slavicized than Peter) -- and actually the Bolsheviks did rename the city Petrograd before settling on Leningrad.

All right, so Sankt Peterburg is not Slavic enough. What about Moskva? Is this an true honest Slavic name? Actually, Moskva does not have a universally accepted Slavic etymolgy; it may very well be of Uralic (specifically, Finno-Ugric) origin.

Or what about Kiev? It means "of Kyi", on a pattern very common with Slavic names. But Kyi itself does not have a clear Slavic etymology. This is very common; names of important rivers, mountains, cities etc. are ancient, and they seldom come from the language of the modern occupants of the land. Think of England; names such as London, Thames, or York are not of English origin: they are much older than the arrival of the Angles, Jutes and Saxons in England. The name of Paris is not of French origin, and it preceded French language by quite a considerable margin. And so on. The name of Rome is not of Latin origin.

So, in practice, if you do not actually know any Slavic tongue, but you want names as used in an actual Slavic country, the best approach is to take a good detailed map of the country in question and lift names of it. You may want to ask around or do a bit of research to learn what the names mean, but lifting obscure names of a real map is for sure the best way.

I may suggest composing placenames using the most productive Slavic suffixes. There are a number of groups of such suffixes:

-ov/-ova/-ovo/-ove/-ev... (Krakow, Kiev, Rostov being the live examples)

-sk/-ska/-sko/-ske/-skoe/-skoye... (Hlinske, Smolensk, Polotsk)

-ts/-tsy/-tsi/-tse... (Chernivtsi, Kamianets, Katowice in Polish spelling)

-ka/-ki/-nia/-nik... (Dubrovnik, Gdynia)

And a number of placename-linked roots as well:

-grad/-gorod (city)

-mest/-mist/-miast (also city)

-most (bridge)

-les/-lis (forest)

-gor/-gora (mountain)

-slav (glory)

etc.

They can be quite freely attached to almost any Slavic name or nominal stem (probably adding or dropping some vowels from the end of the stem for ease of pronounciation). Like Dubograd or Krasnomost. Or Miasoslav. Or even stack them all together to produce something like Zelenogradovskoe or Staromestnitski (a bit unnatural but still very Slavic-sounding and understandable).

There is also a kind of (approximate) rule by which names ending in -a are feminine, -o or -e are neuter, names ending in a consonant (including consonant -y) are masculine and names ending in -i or (vowel) -y are generally plural. This may help create more complex, multiword constructs consisting of an Adjective and a Noun by picking correct gender form of the Adjective.