(Far as I know) Surnames are, at least generally/historically, written with the same kanji and not changed. It'd be like adding a silent h or a to an English last name randomly, but weirder. The kanji can change the meaning or etymology, though. You can have two words that are homophones but different spelling in English, or spelling/kanji in sushi-language. That's what makes it extra difficult.
After looking into it a little bit, most of the names I double checked are well-known locations/cities, surnames (that often double as or originate from locations, i.e. toponymic names,) or the names of well-known people/characters/things. So I think Selebus most likely racked his brain for or googled common names and things to use for the characters that fit the matching initials thing. That's also the simplest explanation. I don't believe he knows any Japanese, but who knows.
If someone more proficient in Japanese recognizes additional meanings / spellings / origins for names that seem plausible, there might be something for a couple of characters. I have one vague possibility in mind, but that's a huge stretch. I'm not qualified to posit anything.