But whatever that process is, there must be a first action, and one cannot ask for consent for that first action

Correct, but that first action need not be grabbing someone's face with your tentacles.

Again, tickling/flirting is not a single atomic action. It's a process which takes time and varies in intensity. It's fine not to have consent for the first few moves if these moves are harmless.

Can Martians really blamed for feeling frustrated at the idea that they should prioritize consent, but it's rude to outright ask for consent?

Well, not blamed, but Martians who are feeling frustrated are just not understanding the way this particular kind of social interaction works.

Flirting is the exchange of deliberately ambiguous signals with the twin purposes of evaluating the other party and negotiating next moves. The signals are ambiguous because it is useful for evaluation purposes and because this provides a way to back out if the comfort level turns out to be not high enough.

Some people (more humans than Martians) find flirting deliciously pleasurable. Some people (more Martians than humans) find flirting maddeningly frustrating. <shrug>

aren't there going to be Martians who think they're getting consent when they're not, and think they're not when they are?

Yes. So what? Do remember that humans can also be good or bad or incompetent at playing this game.

Basically, this system rewards the Martians with the lowest threshold for believing that they have gotten consent.

No, I don't think so at all. I think that Martians with "the lowest threshold for believing that they have gotten consent" just get slapped a lot.