If he can't perform any actions or move, then he hasn't taken a turn.
If his initiative came up in the order and he CHOSE to do nothing, then he took his turn. But if he is HELD or otherwise INCAPACITATED and prevented from doing anything (especially from doing anything to defend himself) then he has not taken his turn, he has had his turn taken FROM him and I would rule that the Assassin has Advantage.
Think logically for a second. Why would it be harder for an Assassin to hit someone who is completely incapable of moving or defending himself in any way than it would be for him to hit someone who is walking down a hallway, oblivious?
If the target had already taken a turn in the combat (meaning, got to actually take some kind of action), then one can assume he is in a fighting stance, has his weapon out, maybe a shield up, that sort of thing. But until he DOES something in combat, he's in the same position (or a worse one) than he was during the surprise round.
Wait, if the target has HOLD PERSON cast on them (or is on some other way held or incapacitated), that means that he's paralyzed, and that EVERYBODY gets advantage against said target. There's no need to worry about whether or not the target has "taken" his turn or not.
Furthermore, anybody attacking the target from within 5' also gets an automatic critical, as per the Paralyzed condition. (Basic Rules 106.) So, the only thing that's not happening here is that the Assassin is not getting an automatic critical on attacks at range, if we determine that, while the target hasn't actually done anything yet, the target is no longer surprised.
To be fair, this could come up.
SCENARIO A:
Party sneaks up on opponents, and attacks. One of the other members of the party fires BEFORE the assassin, thereby alerting the opponents and starting combat, though the opponents are surprised. Initiative is rolled, and now actions take place in initiative order. The wizard gets to act before TARGET A and ASSASSIN, casting Hold Person on TARGET A. TARGET A's turn is next. He cannot act, both because he is surprised, but also because he is Paralyzed and Incapacitated. At the end of his turn, he fails his saving throw, so he is still Paralyzed and unable to take reactions (even though the fact that he was surprised no longer keeps him from taking reactions.) Now the ASSASSIN acts. He doesn't want to engage TARGET A in melee, so he fires an arrow. He has advantage, because TARGET A is Paralyzed. Is TARGET A still surprised, thereby giving him an automatic critical hit?
I'd agree that, by the rules, probably not, as TARGET A had his turn (we know this because he failed his saving throw at the end of it, as dictated by the hold person spell.) On the other hand, by the fiction, I'd say that doesn't really make sense and give the Assassin the automatic critical.
On the other hand, why is anybody doing anything before your Assassin has a chance to fire from hiding? That would have avoided this whole mess in the first place. That is the play when you have an assassin. The assassin shoots first.
SCENARIO B:
ASSASSIN opens combat with a ranged attack on TARGET A. Advantage, auto-crit. Before TARGET A's turn comes up, HOLD PERSON is cast, and he is Paralyzed. TARGET A fails his saving throw, and remains paralyzed until his next turn. ASSASSIN, having led initiative, gets to act again. He doesn't want to close to melee with TARGET A, because there are other opponents nearby, or he is more than 60 feet away. He fires. He has advantage (Paralyzed), but is TARGET A still surprised? Does he get the auto-crit. Good question! I think the "rules" support more that he is not surprised than that he is surprised — again, his turn has passed. On the other hand, I agree, is TARGET A any less vulnerable now than he was 6 seconds ago? Well, the one difference is that the other combatants, the ones who are discouraging ASSASSIN from just walking up and slitting TARGET A's throat, are definitely not surprised anymore (unless they've all been held?). As a result, that has changed the dynamic of the battle enough to make things a little harder for the Assassin. Might justify not giving the auto-crit to an attack from range, but, depending on the circumstances, I could rule either way, just in the interests of common sense.
My apologies if I am mis-reading your post and that is not what we're talking about. I'll admit that I find the construction of hypothetical scenarios to illustrate a problematic reading of a rule to be a little confusing. At the end of the day, at the table, you go with what makes the most sense.
While I disagree with Celtavian's assessment that the ruling supported by Mearls and Co makes the Assassin a worthless class, I certainly agree that, at the end of the day, it doesn't
really matter, and the rules, in this case, as in many other cases, allow multiple interpretations. Use whichever one makes the most sense, and works the best at your table. The Assassins in my game contributed a ton, and we ran things more or less under the more conservative ruling.
I will say my biggest complaint about the Assassin. By giving them a class feature that is so dependent on something rather subjective and complex, it can make for some unpleasant arguments at the table. I don't necessarily think there's much to be done for this while sticking to the design goals of 5e — happy to see attempts, but rules on stealth (and consequently surprise) seem to be either somewhat nonsensical or extremely detailed. I'd just say, if you have a player who is really looking at maximizing damage at all costs, and that player will grind things to a halt when that big damage spike doesn't go his way, encourage that player not to play an Assassin.
