It's hard to find fault with either side for the core problem of not fitting in. However, everything else could have been handled better. This is a learning experience.
First, hiring people based on interviews is known to be a bad procedure. To determine if a person fits a company, you have to let them do some actual work first. Working remote for a period of time is good, but if you're looking for an on-site employee: fly them out, pay them and cover all their expenses for a week, and have them work at least three days. Both sides could have figured out so much about each other if you had only done this.
Then, if someone still turns out to be a bad fit long-term, firing that person is a good decision. Both as a CEO and as the company, you have to take the high road, and make sure you're way more generous than you need to be (especially if that employee moved to another country for you). Clearly you went a step in the right direction there as you stated, but it's still not enough. You should have sat down with that guy and figured out together what it would take to get him back home as smoothly as possible.
Finally, your communication style. It's hard to come out on top when you're faced with this kind of criticism. But keep in mind that you allowed this situation to develop in the first place. While it's certainly your responsibility to raise buzz and sound enthusiastic on behalf of your own company, don't fall into the trap of congratulating yourself too much. We're here because something went wrong, not because everything is beyond awesome over there. Acknowledge that. Implement measures to avoid this in the future. And "a position just opened up :)" is certainly not the right tone at the moment.