Let $M$ be a closed manifold equipped with an affine connection $\nabla$. Let $X \in \Gamma(TM)$, and suppose $X$ is a parallel vector field, i.e. $\nabla X=0$.
Is it true that the flow of $X$ preserves the connection? i.e. let $\phi_t$ be the flow of $X$. Is it true that $\phi_t^* \nabla=\nabla$?
Here, for a given diffeomorphism $\phi:M \to M$, I define $\phi^* \nabla$ by requiring
$$ \phi_*\big((\phi^* \nabla)_XY\big)= \nabla_{\phi_* X}\phi_* Y,$$ where $\phi_*$ is the pushforward operation.
(I think this is the 'right' definition).
What about the converse, that is suppose that $\phi_t^* \nabla=\nabla$. Is $X$ parallel?
I am not sure how to compute the 'variational derivative' $\frac{d}{dt}|_{t=0}\phi_t^* \nabla$.
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:
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.