How about:
...and then he moved to Greensea.
There is no absolute reason to mention that it is a town. Most readers will pick up on that. Especially if you make it clear in further description as your story goes on, or whatnot. But this site is not for writing advice, and even this answer is an opinion.
Other than that, the most common way to put it is probably:
...and then he moved to the town of Greensea.
with
...and then he moved to Greensea town.
being used in rare occasions.
EDIT TO ADD: This whole notion of Use the indefinite article when you mention something for the first time is an example of a grammar "rule" gone mad. It is not even a rule. It is a writing guideline But even then, it does not apply to towns and cities. Also, it is also true that at least 2 out of 3 "first mentions" of any noun are with the, the most commonly used word in English. Just read anything in English. (Sorry if you were not thinking of that rule, but it comes up over and over in questions about article usage.)