I think the answers to your first two questions are yes, there is always a codifferential; and no, there is not always a Hodge decomposition. I don't know anything about the Einstein manifold case.
Let's say $E$ is a vector bundle over $M$ with metric and compatible connection $\nabla$. ($E$ could be some tensor bundle with $\nabla$ induced from the Levi-Civita connection, for example.) As you say, $\nabla$ gives an exterior derivative $d^\nabla$ on $E$-valued differential forms that obeys the Leibniz rule
$$ d^\nabla (\omega \otimes e) = d\omega \otimes e + (-1)^{\text{deg} \omega} \omega \wedge \nabla e ,$$
where $\omega$ is a homogeneous form and $e$ is a section of $E$, and $\omega \wedge \nabla e$ means $\sum_i (\omega \wedge dx^i) \otimes \nabla_{\partial_i} e$.
For each degree of forms $k$, you can view $d^\nabla$ as a map $d^\nabla: C^\infty( \Lambda^k \otimes E) \to C^\infty( \Lambda^{k+1} \otimes E)$. Using the metrics, each of those spaces of sections are endowed with $L^2$ inner products. Then $d^\nabla$ always has a formal $L^2$-adjoint $\delta^\nabla$ going the other way: $\delta^\nabla: C^\infty( \Lambda^{k+1} \otimes E) \to C^\infty( \Lambda^k \otimes E)$.
(Note the space of smooth sections can be completed to the space of $L^2$ sections, but $d^\nabla$ and $\delta^\nabla$ are unbounded operators and can generally only be defined on some dense subspace of that $L^2$ space.)
So you can always define $d^\nabla$ and its formal adjoint $\delta^\nabla$. The issue is that $d^\nabla$ squares to zero if and only if the connection $\nabla$ on $E$ is flat, meaning its curvature is zero. (Flat vector bundles $E$, i.e., bundles on which there exists a flat connection, are relatively scarce.) We need $d^\nabla$ to square to zero to even attempt to define the de Rham cohomology of $E$-valued forms, and to have nice properties like the Hodge decomposition. (I want to say that the "Dirac operator" $D = d^\nabla + \delta^\nabla$ and the "Laplacian" $\Delta = D^2$ are not elliptic unless $d^\nabla$ squares to zero, but I need to think about that.)
I don't have a good reference for this at hand, although the Wikipedia article on bundle-valued forms might be useful.
The relation is as follows. Consider the case $M=\mathbb{R}^n$, where $\nabla$ is the standard connection. Namely, $\nabla$ is the usual derivative. Let $\gamma:I\to\mathbb{R}^n$ be a regular path, and let $X$ be a vector field along $\gamma$. Then $X$ is parallel, in the sense that its covariant derivative vanishes, if and only if its values along $\gamma$ are parallel to one another, in the more naive sense.
Best Answer
As Mike Miller says, vector fields with $\nabla_XX=0$ are very special. For such a vector field, every integral curve is a geodesic. In the plane, for example, what does such a vector field look like? The direction of the vector field has to be constant, and the magnitude can only change in the direction perpendicular to $X$. In other words, $X$ looks like a bunch of parallel stripes, with each stripe having constant magnitude, such as $X(x,y) = (y^2,0).$
There are several intuitive physical interpretations of $X$:
Consider the case where you are on a submanifold of $\mathbb{R}^3$. Put a particle at a point $p$ on the manifold and give it initial velocity $X(p)$. Let the particle travel inertially over the manifold, constraining it to stay on the manifold and not "lift off" into ambient space, i.e. at every point in time, apply just enough acceleration in the normal direction to the manifold to keep the particle's velocity tangent to the manifold. (Think of a magnetic ball bearing, rolling over a sheet of steel in the shape of your manifold). Then the particle will travel along integral curves of $X$, that is its velocity at any time $t$ will be $X(p(t))$.
Cover the manifold in (infinitely compressible) fluid, and give the fluid initial velocity $X$. Now allow the fluid to flow for any amount of time $t$ without any forces acting on it. The fluid velocity at time $t$ will look exactly the same as at time $0$, $X(t)=X$.
When $\nabla_XX \neq 0$, the covariant derivative gives you the failure, at that point, of the vector field to have geodesic integral curves; in interpretation #1 above, for instance, it's the tangential force you must apply to the particle to make it follow the vector field with velocity $X(p(t))$. In interpretation #2, it gives you the negative time derivative of the fluid velocity at a given point (the acceleration felt by fluid particles at that point).