Are the fermions in 4D Euclidean $mathcal{N}=4$ SYM Majorana? If not, what are they?

The statement about not having Majorana fermions in 4d euclidean space is misleading. In the usual Minkowski space Majorana representation the gamma matrices are all purely imaginary (purely real in the less-used (-,+,+,+) metric). The Minkowski space operator-valued charge conjugate fermion field is defined by $$psi^c= {mathcal C}^{-1}barpsi^T\ (barpsi)^c=-psi^T {mathcal C} $$where ${mathcal C}$ is a matrix such that $$ {mathcal C} gamma^mu{mathcal C}^{-1}= -(gamma^mu)^T. $$

The field $psi$ represents a Majorana particle when $psi=psi^c$. Consistency of this property requires that $(psi^c)^c=psi$ and this in turn requires that ${mathcal C}$ be skew symmetric -- something that happens only in $d=2,3,4$ dimensions (mod 8).

In the Euclidean path integral for a Dirac field $barpsi$ and $psi$ are independent Grassman variables. To get a Euclidean Majorana field we simply define $barpsi = -{mathcal C}psi^T$ so that $psi$ and $bar psi$ are no longer independent.

We can take the action for a Euclidean Majorana fermion to be $$ S= int d^4x left{- frac 12 psi^T {mathcal C}(gamma^mu partial_mu+m)psi right}. $$ In order for this expression not to vanish due to the anticommutation property of the Grassman $psi$ we need the operator $$ D= {mathcal C}(gamma^mu partial_mu+m) $$ to be skew symmetric in function space (where $partial_mu^T=-partial_mu)$). This only occurs in $d=2,3,4$ (mod 8). Thus Euclidean Grassman-valued Majorana fermions only exist in exactly the same dimensions as their Minkowski operator-valued bretheren. After performing the Berezin/Grassman integral we get ${rm Det} (gamma^mu partial_mu+m)$ for a Dirac field and ${rm Pf}[{mathcal C}(gamma^mu partial_mu+m)]propto sqrt{ {rm Det} (gamma^mu partial_mu+m)}$ for the Majorana field.

The same is true for psudo-Majorana fermions which are defined using the ${mathcal T}$ matrix that obeys $$ {mathcal T}gamma^mu {mathcal T}^{-1}= +(gamma^mu)^T $$ The resulting Euclidean action $$ S= int d^4x left{+ frac 12 psi^T {mathcal T}(gamma^mu partial_mu)psi right} $$ is non-vanishing only when ${mathcal T}$ is symmetric and this requires $d=8,9,10$ (mod 8) which is again the condition for the existence of Minkowski operator-valued pseudo-Majorana fermions. (Note that pseudo-Majorana's are necessarily massless)

The apparent contradiction in your cited paper is because many authors identify "Majorana" with some sort of reality condition on the gamma matrices and so worry about the reality properties of the Clifford algebras ${rm Cl}(p,q)$ which describe the properties of gamma matrices when the metric has $p$ plus signs and $q$ negative ones. These reality conditions depend intricately on $p-q$ (mod 8). This is nice mathematics, but the physical Majorana condition requires that the analytic continuation of the Euclidean path-integral correlators to the Minkowski region of momentum space coincide with the Minkowski-computed correlators, and this is related to the symmetry properties of ${mathcal C}$ and ${mathcal T}$ which are indifferent to the $pm$ signs in the metric.