For a tangent vector $\bf v$ at a point $x\in\Gamma$, and a smooth (real valued) function $f$ defined on an open neighborhood of $x$, one can define
$\nabla_{\bf v}f:=\langle {\bf v},\nabla_\Gamma f\rangle$ (the scalar product).
Note that both $\bf v$ and $\nabla_\Gamma f$ already lie in the tangent space of $\Gamma$, and hence only the scalar product of $T_x\Gamma$ is used.
Then, for a vector field $Y$ (on $\Gamma$), if given by coordinate functions $(f_i)_{i=1}^n$, define $\nabla_{\bf v}Y := (\nabla_{\bf v} f_i)_i$.
Finally, for a point $x\in\Gamma$, set $(\nabla_X Y)_p := \nabla_{Xp}Y$.
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
This doesn't really have anything to do with connections. Notice here that the $\nabla$ does not refer to a connection but instead denotes the gradient of a function, which is a vector field, and which can be defined for a manifold $M$ with metric $g$ by $$ g(\nabla f, X) = df(X) $$ where $X$ is a vector field on $M$. Unfortunately the symbol $\nabla$ is also used for connections and in that context $\nabla f$ is actually equal to $df$ for any connection $\nabla$ (basically by definition).
The usual metric on $\mathbb R^n$ restricts to a metric on the hypersurface $M$. Then the hypersurface gradient of $f$ is just the gradient of $f$ with respect to this metric (it'd be a good exercise to run through the definitions and check this); notice that in forming it you're taking the entire gradient of $f$ and then subtracting off the normal part, getting something tangent to $M$.