I Said Do You Speaka My Language
One thing about names is that they are pronounced like regular words. That's because often names actually are regular words. Consider, for example, that silly trope where boy meets exotic girl and she says her name is Mortihomoalbus or whatever and the boy asks, "What does that mean?" Invariable the girl has some cheeseball answer.
Many names are derive from words already in common usage in that language. For example, a lot of family names come from trades (like Baker). A lot of place names are descriptive (like Buena Vista). And a lot of family names incorporate their place of origin (like names of nobility but also like Jesus of Nazareth).
Hooked On Phonics
Given the above, you need to start stringing some syllables together. You said you don't want to use real Earth names so I recommend you start imagining what the language of your culture sounds like. You can start off really basic and bombastic.
I don't mean to offend, but consider for example how the movie "Team America" characterized Arabic as "durga durga," or how the Muppets Swedish Chef made a lot of "herdy birdy" sounds. Then, consider all the other the awful stereotypes that people have when they are making fun of Chinese-speakers, the French, Jamaicans, and other languages. These sounds are the types of sounds (whether real or imagined) that are associated with a culture, which includes both regular words and also names.
A Rose is but A Rosé
More on the above point, consider also that different cultures will literally convert the same name to fit their language. Like the name "John." A name from the Bible, originally Hebrew "Yochanan" which then grew in popularity among Eastern Orthodox so you get "Yannis" and so forth but then also the rest of Europe where you get the German "Johann," the French "Jean," and the Italian "Gian."
How Do You Identify Yourself
Which brings me to my last point: why on Earth would an English guy have a Hebrew name? You know why: Christianity. Europe (and the Middle East for that matter) was crazy about religion for a long ass time and the plethora of names based on religious characters is a reflection of that.
The Borg are super into order and "thinking as one," and their names are reflective of their hierarchical predilections. Cartoon cavemen are super into being stupid but strong and so you use onomatopoeia to get names that sound like bashing something with a club, "Klag" and what have you. (I guess Klingons are too, but I didn't want to lean on Star Trek too much.)
Don't get me started on pop-culture versions of Native American names, "Sitting Bull" turns into "Dances with Wolves" and or whatever. 'Cos we all know Native Americans cry a tear when you litter. Ugh.
The point is, names often come from whatever it is that the culture is holds in high regard. (Consider, for example, the bastard names of Game of Thrones.)
But to summarize, if you are going to make up new names that are not based on existing Earth cultures, then I think you think about that culture's language and ideals. You can also consider historical events that brought cultures together, either through religion, conquest, slavery, trade, etc. Good luck!