EDIT: I ended up changing my game’s name
You sue the inglorious bastards. 
You choose another name.
[I ended up changing my game’s name]
Change the name unless you want people to look up your game and find the wrong one and give some one else the money. As a general rule: it tends to backfire to pick such simple names for product titles, chances are some one already used it.
You can add a subtitle if you insist on retaining the word: Paragon: Darkness of Space or whatever (you the one making the game, surely you know what can fit there.)
Well, you could friendly ask the developers if they are willing to change the name.
It doesn’t matter who started first, only who got to market or got the word out there first.
In this case you need to change your games name.
First off, I know your game and love it. It’s beautiful. I’d do what was mentioned above with some proof that you started first. But, unfortunately, the gaming business isn’t fair. I wouldn’t try too hard to get the name, though.
I would find where they live and dropkick their ass
Ask if they’re willing to change the name.
Change your name.
Add a subtitle which the game can possibly be known as instead of people knowing it as the name used by the other person.
On the other hand, keep the name and if they find it show proof that you had it first 
.
[I ended up changing my game’s name]
Started your game first means absolutely NOTHING. They could say the same thing they ‘started it before you’. It doesn’t afford you any sort of protection.
The only protection you could have is to TRADEMARK YOUR NAME. After that, now you have the legal basis to sue and win. If not, then tough luck, its fair game as far as law is concern. Best course of action is to just rename your game.
<I ended up changing the game’s name!>
I suggest a battle to the death
Alternative: don’t give your game names that are common single word fantasy terms since odds are they’re all taken and it’ll make SEO really hard.
<I ended up changing the game’s name!>
Do what Starsman suggests. Add a subtitle, ‘Paragon: Infinite Space’ or whatever. FWIW - This thread could be used against you as proof that you knew of the other games existence BEFORE you released your title. Sure, it’s unlikely anyone will care, but if they do, you be coughing up $1000s in legal fees. You can stand on principle, but it may cost you a lot of time and effort.
Gigi.
This.
Back when I was at GG, we ended up doing that for Legions : Fallen Empire. It was in development for a fair amount of time and it was always “Legions”. But it there were a couple of other games, though different, using that name. Using the subtitle ended up working well, and we were able to trademark that. Trying to trademark a single dictionary word can be tricky.
Rename it to something like Project Paragon.
<I ended up changing the game’s name!>