Das Thema Namensbildung, und der damit verbundene Sprachgebrauch ist wirklich ein sehr interessantes, komplexes Thema.
Tollkien hat z.b. Mittlererde nur erschaffen, um einen Rahmen für eine von ihm erfundene Sprache zu schaffen. (nicht wie in unserem Fall anders herrum)
Namen bleiben bei uns vor allem dann haften (mal abgesehen von den Kriterien in TrueMG) wenn deren Struktur der Struktur unserer Worte gleicht. Hierbei vor allem die gänige Reihenfolge von Selbstlauten und Umlauten.Auch ob ein Umlaut stimmhaft oder stimmlos ist, spielt hier eine Rolle. Bestimmte Kombinationen sind sehr häufig, andere eher ungewöhnlich z.b. enden viel Frauen-Namen im deutschen auf -na oder -ne (Sabine/na, Mona, Susanna/ne, Carina ect.) für unser Gehirn klingen also Namen mit diesen Endungen vertraut, und auserdem weiblich. Darauf kann man dann aufbauen oder abwandeln. (so sind viele Namen im übrigen wirklich entstanden) Aus "Sabina" wird dann zum Beispiel "Sarena" Würdest du diesen Namen nun für einen männlichen Helden nemen, wäre dieser nur schwer zu merken und würde "komisch" klingen, als Frauenname für einen Helden jedoch "vertraut" und damit besser einprägsam.
Du siehst, markante "Fantasienamen" zu erfinden ist sehr komplex. Also ist wohl die einfachste Methode tatsächlich die von TrueMG beschriebene.
Was auch eine gute Möglichkeit ist, hier mal rein zu schaun.
beliebte-vornamen.de
Da kannst du typische Vornamen für alle möglichen Länder suchen z.b. Hwaiianische, und dann all deinen Charaktern solche Namen geben
unter vorname.com kannst du nach gänigen Namen suchen, und dir dann "exotischere" Abwandlungen anzeigen lassen.