So essentially, the model theoretic proof, if I'm not missing anything, is sort of a "rewording" of the same argument given in the OP (I omitted some details, but it should be clear how to conclude once that the problem has been embedded into $\mathbb Q^\kappa$), right? Still, interesting and quite instructive. Thank you!

@Andy Putman. There seems to be a minor issue here, but it is probably due to a mere question of dictionary, so let me ask: What do you mean by a surface group? More specifically, does your definition include the fundamental group of the projective plane? If so, it is not true that all surface groups are bi-orderable. On another hand, can you provide historical evidence that Thurston had discovered that braid groups are left-orderable before Dehornoy did? Thanks in advance.

Here is another class for which the general "conjecture" holds: Strictly totally orderable magmas, where we say that $\mathbb A$ is strictly totally orderable if there exists a total order $\preceq$ on $A$ such that $a + c \prec b + c$ and $c + a \prec c + b$ for all $a,b,c \in A$ with $a \prec b$. Then, it seems reasonable to ask: What about torsion-free magmas?

@GH. You were right. I followed your advice and wrote to Ruzsa. As far as groups are concerned, he has a theorem, whose proof doesn't rely on the Feit-Thompson theorem, which implies at once that Károlyi's theorem extends to arbitrary groups. So then, let me update the OP.

OK, but Smith's definition of a quasigroup is the same as the definition given on Wiki.en (en.wikipedia.org/wiki/Quasigroup). That is, a quasigroup (in the sense of Smith) is a magma in which every element is split, while it doesn't need to be cancellative. In any case, you're right, and my example is a non-unital, commutative, cancellative quasigroup (again, in the sense of Smith).

As per your question, the answer is no. For, consider a set $S$ with three elements $a$, $b$ and $c$, and let $\diamond$ be the binary operation on $S$ given by the following (Cayley) table: $$\begin{array}{c|ccc} \diamond & a & b & c \\ \hline a & b & a & c \\ b & a & c & b \\ c & c & b & a \end{array}$$ Now, a magma $\mathbb A=(A,\ast)$ is cancellative if no row or column of its table contains repetitions, while an element $e \in A$ is a left (resp., right) identity (for $\mathbb A$) if it leaves unchanged its own row (resp., column) in the table of $\mathbb A$.

Thanks for the references. Just to be sure that we're speaking the same language: What do you mean by a quasigroup? Also, why do you mention that a finite cancellative magma should have a one sided unit? To wit, what's the link with the questions in the OP? Let it be as it may, if my guess is correct and you're using "unit" for "identity" (what else otherwise?), then I don't know the answer to your question.

[...] $\mathbb A=(A,\ast)$ is a (commutative) magma, and $Y\ast Y=\{z_0\}$, but $p(\mathbb A)\ge n$, so the general "conjecture" is disproved for $n \ge 2$ and $|Y| \ge 2$. Notice that $\mathbb A$ is non-associative for $n\ge 2$, since then $(z_{n-2}\ast z_{n-2})\ast z_{n-1}=z_0$, while $z_{n-2}\ast(z_{n-2}\ast z_{n-1})=z_{n-1}$. It is then natural to ask whether the general "conjecture" holds true if the ambient magma is associative. I will update the OP to summarize this exchange for others.

So your 2nd sentence was referring to $(2,2)$-deficient magmas. Désolé, je ne l'avais pas entendu ! And thank you for the elegant example, which in turn implies a counterexample to the general "conjecture". For, let $\{X,Y\}$ be a non-trivial partition of $A$ with $n:=|X|<\infty$, and $(z_i)_{i\in\alpha}$ a numbering of $A$ s.t. $X=\{z_0,\ldots,z_{n-1}\}$, where $\alpha$ is the ordinal of $A$. We define a binary operation $\ast$ on $A$ as follows: For $i,j\in \alpha$ we take $z_i\ast z_j:=z_0$ if $\max(i,j)\ge n$ and $z_i\ast z_j:=z_{(\max(i,j)+1)\,\bmod\,n}$ otherwise. Then, [...]

Then thanks for the hints; now, your point is clear to me too. So, let me ask a couple more of questions. You wrote that "[...] being deficient turns out to be relatively rare", but one line later I read that you "[...] discovered those magmas are not rare". Should I consider as correct the 1st or the 2nd sentence? If the 2nd sentence is the right one, then it's likely that you had found out a way to construct a lot of deficient magmas, didn't you? Then, let me repeat my question from the above: Would you mention a class of examples of deficient magmas with no non-trivial idempotents?

[...] "conjecture", but this is somewhat trivial. So let us focus on the case of $(m,n)$-deficient magmas with no non-trivial idempotents: Are you suggesting that these could verify/provide a counterexample for the general "conjecture"? Would you mention a class of examples of deficient magmas with no non-trivial idempotents? Also, in which sense the work that you're referring to at the end of your answer should hopefully fully address Q2, considering that it's not even known, for what I can say, whether or not it holds for infinite non-commutative groups?

I don't quite understand what exactly you're claiming. If I take it correctly, I'd say that, given $m,n\in\mathbb N$ with $m\le n$, an $(m,n)$-deficient magma is a magma $\mathbb A=(A,\ast)$ for which there exists $X\subseteq A$ with $m\le |X|\le n$ s.t. $|X|\ge |X\ast X|$; in particular, you're looking at the case where $3\le m$, $n<|A|<\infty$. So, e.g., if $\mathbb A$ is a zero-left or zero-right sgrp (and hence a band), then it's $(m,n)$-deficient as long as $n\le |A|$. And it's clear that if $\mathbb A$ has at least one non-trivial idempotent then it does certainly satisfy the [...]