Since I read Lin Carter's worldbuilding advice in Imaginary Worlds, at least, I've had an interest in names and neologisms in settings. I certainly have an interest in the "conlang" end of things--the world of Professors Barker and Tolkien appeal to me--but I don't think it's necessary to invent a language or even partial devise one to have character and place names that seem plausibly like they might arise from a an actual language.
Carter points out in his essay, names need to have an appropriateness to them. He uses the example of Stonehenge (the location), and asks the reader to imagine it was named Piccadilly. Stonehenge seems a much more appropriate name for the place, not the least because it has "stone" as a component. Obviously, the "fit" of a name depends on preconceptions arising from one's native language, but also one's personal preferences. There are people that feel Clark Ashton Smith was horrible at invented names, and plenty (Carter included) who think he was a master of them.
In coming up with names I try to first consider this aspect of appropriateness: What vibe do I want the name or names to convey? The second thing I try to do is give them a sense of linguistic cohesiveness, as if they might come from the same language.
For the imperial Vokun in Strange Stars, I wanted them to have names that suggested a tradition-bound, decadent, warrior culture. I thought longer names with some "heavier" (to the English speaker) sounds would fit the bill. I wound up using a list of Old Avestan names as my base, adding in some names from other sources, mixing and matching syllables and selecting mostly longer ones that I further tweaked to taste. Online name generators that accept a list of words as an input are good for inspiration, but they seldom provide a lot of "keepers" without tweaking. I wound up with names like this: Artazosthra, Ishramis, Jannaxa, Valakasta, Vahupareshta, Zrayangashamesh.
For my as yet unnamed science fantasy setting, I wanted most of the human names to have an easy and obvious rhythm and length for English speakers, but not generally be actual (or at least common) English names. the naming styles of Edmond Hamilton and Jack Vance were particular influences here, leading to names like: Glattis Malva, Godo Shrune, Yreul Dahut, and Festeu Harfo. The place names similarly were devised to be like English place names, but not actually be English place names.
The names of the nonhumans in this setting (like the various clades in the Strange Stars) had names suggesting they came from different languages: hohmmkudhuk, ythlaxu, and hwaopt are "weird" in some way for English speakers, but trell and ieldra are much easier. Not every alien should have a name like something out of Marc Okrand's Klingon!
Of course, there are a lot of other things to consider. Carter's essay suggests things like trying to spread them out over the alphabet to make them distinct.