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.
Best Answer
To answer your question: no, on a trivial vector bundle, there are covariant derivatives that are not "the exterior derivative". Generally, if there are two connections $\nabla, \nabla'$ on your vector bundle $E$, then their difference is an $\text{End}(E)$-valued 1-form, i.e. an element of $\Omega^1(M;\text{End}(E))$, and conversely, you can obtain a connection by adding such a 1-form to another connection. This means that the connections on $E$ form an affine space modelled on $\Omega^1(M;\text{End}(E))$, i.e. picking a base point (or canonical choice of connection) we can identify the two vector spaces.
The reason why I put "the exterior derivative" in quotes, btw., is that, since sections of $E$ take values in $E$, they are not real functions, and can therefore not really be differentiated. What is usually meant is that for a trivial bundle, there is usually a canonical choice $(e_1,\dots,e_r)$ of global frame (i.e. $r$ sections of $E$ that provide a basis in each point). In the case of $M\times\mathbb{R}^r$ those are usually defined as $e_i(p) := (p, \epsilon_i)$ where $\epsilon_i$ is the $i$-th unit vector of $\mathbb{R}^n$. Anyway, you can now define a connection $\nabla$ (the so-called canonical connection) by requiring that $\nabla_X e_i=0$ for all $i$. This implies that for any section $s=\sum_{i=1}^r f_i e_i$ the covariant derivative looks like $$\nabla_X s = \sum_{i=1}^r \nabla_X(f_ie_i) = \sum_{i=1}^r X(f_i)e_i + f_i\nabla_X e_i = \sum_{i=1}^r X(f_i)e_i = \sum_{i=1}^r df_i (X) e_i,$$ or in other words that $\nabla s = \sum_{i=1}^r df_i\otimes e_i$, which is where the shorthand $\nabla=d$ comes from. And since any connection can now be written as $\nabla+\theta$ for a suitable $\theta\in\Omega^1(M; \text{End}(E))$, this is where the shorthand of $d+\theta$ for a general connection comes from.