The quantity you call the "variational derivative" is just the Lie derivative of $\nabla$ along $X$: This is the tensor field $\mathcal L_X \nabla: TM \to T^*M \otimes TM$ characterized by
$$(\mathcal L_X \nabla)(Y) = [\mathcal L_X, \nabla] Y = \mathcal L_X (\nabla Y) - \nabla \mathcal L_X Y ,$$ which measures the failure of $\mathcal L_X$ to commute with $\nabla$, that is, the infinitesimal failure of the flow of $X$ to preserve $\nabla$. (For more see these expository notes of Mike Eastwood, which are ultimately concerned with infinitesimal projective symmetries, that is, vector fields whose flow preserves the projective class of a connection.) It's straightforward to verify that this quantity really is tensorial (in $Y$).
If $\nabla$ is torsion-free, which we henceforth assume, we may express the Lie derivative of a vector field in terms of $\nabla$, and in fact in this case the object in $T^*M \otimes T^*M \otimes TM$ obtained by dualizing is actually in $S^2 T^*M \otimes TM$ (this dualized object is the infinitesimal version of the difference tensor between two connections). A straightforward calculation gives that
$$(\mathcal L_X \nabla)_{ab}{}^c = \nabla_a \nabla_b X^c + \color{red}{R_{da}{}^c{}_b X^d} ,$$
where $R$ is the curvature tensor.
In the case that $X$ is parallel, the first term on the r.h.s. vanishes by definition, and so the preservation of $\nabla$ by the flow of $X$ is governed (at least in the torsion-free case) precisely by the vanishing of $\color{red}{R_{da}{}^c{}_b X^d}$. In general this quantity need not be zero:
Example Consider the (torsion-free) connection $\nabla$ on $\Bbb R^2$ characterized by
$$\nabla_{\partial_1} \partial_1 = x^2 \partial_1$$
and $\nabla_{\partial_i} \partial_j = 0$ for all other $(i, j)$. We can read off immediately that $\partial_2$ is parallel w.r.t. $\nabla$, but computing gives that $R = - dx^1 \wedge dx^2 \otimes \partial_1 \otimes dx^1$, so $\mathcal L_X \nabla = dx^1 \otimes \partial_1 \otimes dx^1 \neq 0$.
On the other hand, if $\nabla$ is the Levi-Civita connection of some metric, the symmetries of a metric curvature tensor allow us to rewrite $\color{red}{R_{da}{}^c{}_b X^d}$ as $g^{ce} g_{af} R_{be}{}^f{}_d X^d$, but this vanishes by the definition of curvature and the condition that $X$ is parallel. In other words, if we specialize to Levi-Civita connections, the answer to the question is always positive.