I've been in this situation a few times in the last several years, where I have had a good, but not good-enough player, and I have tried a new approach to the dismissal each time. What follows is what I should have done in every instance.
First, go with your gut and end it ASAP, do not try to mentor, do not try to grow them, just end it and move on. I have spent too much time, effort, and money trying to bring the performance of B-players up to A-player status. If someone has hustle, then you can point out shortcomings and they will stay up all night making it perfect. That's an A-player in the rough; don't cut those players. If you point out shortcomings and they continue to deliver mediocrity over and over, cut them and move on.
Recognize who is ambitious and who is not, and place people in appropriate roles. There's nothing wrong with people who lack ambition, but they can't hold critical roles in high-performing teams, they drag the ambitious, hard-working, self-motivated A-players down.
I agree with many other commenters that the right thing to do is to be honest that it's not going to work out, and offer a severance package. I disagree with some severance numbers that have been suggested... the standard number is a week of severance for each year of service - that's what I go with.
However, if the person made significant concessions to work with you, for example, if they moved their family cross-country to take the job with you, then more severance is appropriate. "Make them whole".
As for delivering the message, my advice is the Band-Aid approach, make it succinct, do it in a place where their co-workers can't overhear, and plan their exit in a way that they don't run into other co-workers. You don't want the person to have to answer "how's it going" as they pack up their desk. I disagree with the long heart-to-heart conversation approach. After just getting canned is not the right time for mentoring. They’ll find support elsewhere, you trying to ease their pain makes it worse. If you like the person and would like to help them, tell them that, but tell them to catch up with you later on and say you’re happy to talk when they’re in a position to. If they want to talk right away, by all means do, but don’t force it on them.
I have never fired someone too soon. In retrospect, I always should have acted faster. The fact that you’re on here asking for advice means that it’s time to act.
Finally, I realize that some of the above may sound ruthless, so let me make three comments on philosophy and _why_ being direct and decisive is the best course of action:
1) It is demoralizing to the rest of the team to see someone reaping the same benefits they get for doing better work. One bad player will poison an entire team. Even nice, pleasant, hard-working people who require too much care and feeding will sap energy from the team.
2) It is not fair to the individual to leave them in a position where they are not succeeding. Leaving someone in a position where they are not cutting it is cruel – s/he will find a better fit elsewhere.
3) In a start-up environment, you simply cannot afford a B-player in any key role. Everyone has to put up at least their own weight, and a single person not doing that reduces your odds of success. A lot has been written on this, so I won’t go on – but one wrong hire can destroy a small company.