**N.B.:** I'm fixing my answer, which was off for two reasons: First, I didn't correctly interpret the OP's notation. (Thanks, Sebastian, for pointing that out!) Second, I didn't check the case when the Jordan normal form of $R$ has blocks of size $2$ or more (i.e., multiple eigen*values* but not multiple eigen*vectors*), and my original answer did not clearly treat this case.

By the way, even and odd dimensions have nothing to do with this problem.

In local coordinates $x^i$ and with connection coefficients $\Gamma^i_{jk}=\Gamma^i_{kj}$ (since the connection is assumed to be torsion-free (aka symmetric)), the formula for covariant derivative of a $(1,1)$-tensor is
$$
\nabla\left(R^i_j\ \frac{\partial\ \ }{\partial x^i}\otimes \mathrm{d}x^j\right)
= \left(\frac{\partial R^i_j}{\partial x^k} + R^\ell_j\Gamma^i_{\ell k}- R^i_{\ell}\Gamma^\ell_{jk}\right)\ \frac{\partial\ \ }{\partial x^i}\otimes \mathrm{d}x^j\otimes \mathrm{d}x^k.
$$
Thus, you want to solve these equations:
$$
R^\ell_j\Gamma^i_{\ell k}- R^\ell_k\Gamma^i_{\ell j} =
\frac{\partial R^i_k}{\partial x^j} - \frac{\partial R^i_j}{\partial x^k}
\qquad\text{and}\qquad
\Gamma^i_{jk}=\Gamma^i_{kj}\,.
$$

Note that the equations with upper index $i$ and upper index $i'\not=i$ do not interact, so what you really want to know is the conditions on a linear transformation $R = (R^i_j)$ in order that the equations
$$
R^\ell_j S_{\ell k}- R^\ell_k S_{\ell j} = A_{jk}
$$
be solvable for a symmetric form $S = (S_{jk})=(S_{kj})$ for any given anti-symmetric form $A = (A_{jk})= (-A_{kj})$. I.e., in matrix form, one wants to solve the equation
$$
RS - SR^T = A
$$
for a symmetric matrix $S$ given any anti-symmetric matrix $A$, so it's a question of when this linear map from symmetric matrices (a vector space of dimension $\tfrac12n(n{+}1)$) to anti-symmetric matrices (a vector space of dimension $\tfrac12n(n{-}1)$) is *surjective*. (For dimension reasons, it could never be an isomorphism.)

This problem is equivariant with respect to the action of $\mathrm{GL}(n,\mathbb{R})$, i.e.,
$$
aRa^{-1} (aSa^T) - (aSa^T)(aRa^{-1})^T = a(RS-SR^T)a^T,
$$
so it suffices to put $R$ in Jordan normal form and check surjectivity of this linear map in this case.

What one finds is that the map is surjective if and only if there do not exist two distinct Jordan blocks belonging to the same eigenvalue. In other words, $R$ should not have two *linearly independent* eigenvectors belonging to the same eigenvalue. It's OK for $R$ to have *generalized* eigenspaces of dimension greater than $1$, but not a true eigenspace of dimension greater than $1$. An equivalent way to express this condition is that the minimal polynomial of $R$ have degree $n$. As expected, this is an open condition on $R$, since it asserts that the $n$ matrices $I,R,\ldots, R^{n-1}$ be linearly independent. Whether the eigenvalues be real or not is immaterial.

Note that, even when $R$ satisfies this condition, the solution $S$ is not unique; there is an $n$-parameter family of solutions. (Which leads, at each point of $M$, to an $n^2$ parameter family of solutions to the original problem.)