A One-Page Language: The Minimum Needed for Consistent Invented Names
The reason invented names feel invented is almost never that any single name is bad. It is that the names do not agree with each other. One has a German shape, the next an Italian one, the third has an apostrophe from nowhere. Readers cannot articulate this, but they feel it as arbitrariness, which is the opposite of the effect you wanted.
Fixing it does not require constructing a language. Full conlanging is a wonderful hobby and enormous overkill for naming. What you need is three decisions and a list, which takes about twenty minutes and then serves the whole project.
Decision one: your sound inventory
Write down the consonants and vowels this culture uses. Crucially, also write down the ones it does not.
The exclusions do most of the work. Real languages have gaps: many have no f, several have no p, plenty have no th, and some have three vowels where English has a dozen. A language missing two or three common English sounds will immediately produce names that feel foreign in a coherent rather than a random way.
A workable starting inventory might be: consonants k, t, s, n, m, l, r, v, h; vowels a, e, i, o. Note what is absent: no b, d, g, p, f, w, y, u, no ch or sh. That single list already guarantees every name you build will sound related to every other.
Choose the inventory to serve the culture's character. Heavy on plosives and back vowels for a harsh people; heavy on liquids and nasals for a lyrical one. This is the point at which the sound-symbolism work pays off, because you are deciding the palette rather than each brushstroke.
Decision two: your syllable shape
Now decide how sounds may be arranged. Linguists write this compactly using C for consonant and V for vowel.
A CV language allows only consonant-vowel syllables, so every word is strictly alternating and ends in a vowel: Kanoli, Tesama, Rivano. It is the simplest possible rule and produces smooth, open, Polynesian-flavoured names.
A CVC language allows a closing consonant, which immediately produces a harder feel: Karnot, Telkan, Ristav.
A CCVC language permits initial clusters and gets consonant-dense and Slavic or Germanic in feel. Whatever you choose, the rule is the constraint that makes the names siblings. Two syllable shapes in one culture is fine; five is no rule at all.
One refinement worth the effort: also decide which consonants may end a syllable. Real languages restrict this heavily, often to nasals and liquids. Allowing any consonant anywhere is the fastest way back to arbitrariness.
Decision three: your meaningful parts
Now build a short list of morphemes, meaningful chunks, using your inventory and syllable rule. Fifteen to twenty is plenty. Cover the things names are actually made of: water, stone, high, low, river, home, dark, light, king, holy, new, old, and two or three suffixes meaning "place of", "child of", and "belonging to".
This is the step that transforms names from strings into vocabulary. Once kar means stone and -eth means place of, you have Kareth, the stone place, and you have it forever. Every subsequent name using kar is silently consistent, and an attentive reader who notices that three place names share an element has just discovered something real about your world with no help from you.
Keep the list somewhere you will actually reopen. The whole benefit is cumulative and evaporates if you invent a new meaning for kar in chapter twelve.
Now generate against the rules
With three decisions made, naming becomes assembly rather than inspiration. Combine morphemes for meaningful names; combine bare syllables from the inventory for names whose meaning has been lost, which every real language has in abundance.
Generators remain useful at this stage, used in a specific way: as a source of raw shapes to filter through your rules rather than as a source of finished names. Pull thirty candidates from a kingdom name generator or an island name generator, then discard everything containing a sound your language lacks and reshape the survivors to fit your syllable rule. What comes out is recognisably yours, and you did not have to invent it from a blank page. The generator supplies variety; your rules supply coherence. Neither alone produces both.
Add a second language and a border
The highest-value addition, once one system works, is a second one that is deliberately different, sharing few sounds with the first. Now put them next to each other geographically.
Everything interesting happens at the seam. Border towns have names in both languages, or one name mangled by the other's phonology. A conquering language leaves its suffixes on conquered places. A trade pidgin produces hybrid names that belong to neither side. Characters from the border have a name from one culture and a surname from the other. None of this requires grammar, only two sound inventories and a map.
How much is enough
Stop when the names are consistent. That is the entire goal. You do not need verb conjugations, you do not need a writing system, and you almost certainly do not need to be able to translate a sentence.
The test is to write twenty names using the system, then have someone look at them alongside five names from a different culture in your world and try to sort them into two piles. If they can, without being told the rule, the system works and you are finished. Twenty minutes of setup, and every name you invent for the rest of the project will belong.