The answer to both of your questions is yes, and I think that it works completely analogously to what describe in the first part of your question. More specifically,
The idea of the trace is the same one that you discuss in the
first part of your question. The "$E$-Hessian" $\nabla^2 \varphi$ is a section of $E
\otimes T^\ast M \otimes T^\ast M$. Use the metric (the musical
isomorphism $\sharp$) to identify $T^\ast M$ with $TM$ and obtain a section
of $E \otimes T^\ast M \otimes TM \cong E \otimes \text{End}(TM)$.
Take the trace of the endomorphism piece to obtain a section of $E$.
Note that $\nabla^2 \phi$ may not be symmetric in its entries, so we have a choice
as to which factor of $T^\ast M$ we apply $\sharp$ to, but this choice is irrelevant once
we take the trace.
In terms of a local frame $\{ e_i \}$ for $TM$, we have
$$ \Delta \phi = \text{tr}_g \nabla^2 \varphi = g^{ij} [\nabla^2 \varphi] (e_i, e_j).$$
Of course, if the frame is orthonormal, this reduces to $[\nabla^2 \varphi] (e_i, e_i)$,
as you stated.
We have a connection $\nabla^E$ on $E$ and the Levi-Civita connection $\nabla^{LC}$ on $T^\ast M$. These induce a connection $\tilde{\nabla}^E$ on
$E \otimes T^\ast M$, which is defined by the "product rule":
$$\tilde{\nabla}^E (\varphi \otimes \omega) = (\nabla^E \varphi) \otimes \omega + \varphi \otimes (\nabla^{LC} \omega)$$
where $\varphi$ is a section of $E$ and $\omega $ is a one-form.
This connection gives a map $\tilde{\nabla}^E: \Gamma(E \otimes T^\ast M) \to \Gamma(E \otimes T^\ast M \otimes T^\ast M)$, and as you guessed, $\nabla^2$ as you defined it is precisely the composition of the connections
$$\tilde{\nabla}^E \circ \nabla^E: \Gamma(E) \to \Gamma(E \otimes T^\ast M) \to \Gamma(E \otimes T^\ast M \otimes T^\ast M).$$
It's a good exercise to prove this!
A note, as much for my own understanding as anything: $\tilde{\nabla}^E$ as defined above is an extension of $\nabla^E$ which maps $\Gamma(E \otimes T^\ast M) \to \Gamma(E \otimes T^\ast M \otimes T^\ast M)$. There is another interesting extension of $\nabla^E$ to $E \otimes T^\ast M$, which I will call $d^E$. $d^E$, in contrast to $\tilde{\nabla}^E$, is a map
$$d^E: \Gamma(E \otimes T^\ast M) \to \Gamma(E \otimes \Lambda^2 T^\ast M),$$
i.e., $d^E$ gives a two-form with $E$-coefficients. More generally, one can define $d^E$ as a map on $E$-valued forms of any degree:
$$d^E: \Gamma(E \otimes \Lambda^k T^\ast M) \to \Gamma(E \otimes \Lambda^{k+1} T^\ast M),$$
defined by
$$d^E(\varphi \otimes \omega) = (\nabla^E \varphi) \wedge \omega + \varphi \otimes (d\omega),$$
where $\wedge$ means "wedge the one-form part of $\nabla^E \varphi$ with $\omega$".
I suppose one should think of $d^E$ as a generalization of the de Rham exterior derivative $d$ on forms. (If $E$ is the trivial bundle $M \times \mathbb{R}$ with trivial connection $\nabla^E = d$, we recover $d$.) Note that $d^E$ does not require a connection on $TM$.
The curvature $R^E$ of the connection $\nabla^E$ is the $\text{End}(E)$-valued two-form defined by the composition
$$R^E:=(d^E)^2 \text{ (or }d^E \circ \nabla^E): \Gamma(E) \to \Gamma(E \otimes T^\ast M) \to \Gamma(E \otimes \Lambda^2 T^\ast M) .$$
It's a standard computation to show that $R^E$ really lives in $\text{End}(E)$, i.e., that it's $C^\infty(M)$-linear, and that
$$ R^E(X,Y) = \nabla^E_X \nabla^E_Y - \nabla^E_Y \nabla^E_Y - \nabla^E_{[X,Y]} $$
As a final remark to relate this back to the Hessian, notice that the antisymmetric part of the Hessian is precisely the curvature, i.e.,
$$[\nabla^2 \varphi](X, Y) - [\nabla^2 \varphi](Y, X) = R^E(X,Y) \varphi.$$
The Hessian of a smooth function is symmetric, which is equivalent to the the fact that the de Rham "curvature" $d^2$ is zero.
References: Here are a couple of books I found useful in reminding myself how some of this works:
- Jost, Riemannian Geometry and Geometric Analysis. See chapter 4.
- Taylor, Partial Differential Equations I. See Appendix C (on his website) and chapter 2.
I think it's much more common to let the last index position be the one introduced by differentiation, not the first. But regardless of which convention you choose, you're never going to have a Leibniz rule for total covariant derivatives of the form $\nabla (T\otimes S) = \nabla T \otimes S + T\otimes \nabla S$. (Notice, for example, that if both $S$ and $T$ have positive rank, then the differentiation index in $\nabla T \otimes S $ is never the last one, and in $T\otimes \nabla S$ it's never the first one.)
The Leibniz rule for covariant derivatives of tensor fields applies to the covariant derivative in the direction of a vector field (or vector):
$$
\nabla_V(S\otimes T) = \nabla_V S \otimes T + S \otimes \nabla_V T.
$$
This is true whether you put the differentiated index last or first (or somewhere else).
Best Answer
If $\nabla$ is a connection on $\mathcal T(M) = \mathcal T(M)^{(1,0)}$, you can induce a connection on $\mathcal T(M)^{(0,1)}$ by
$$ (\nabla _X \alpha) (Y)= X(\alpha(Y)) - \alpha(\nabla _X Y)$$
where $\alpha$ is a one form and $Y$ is a vector field. You can check that $\nabla _X \alpha$ so defined is $C^\infty(M)$-linear, thus $\nabla_X\alpha \in \mathcal T(M)^{(0,1)}$.
In general if you have two vector bundles $E, F$ with connection $\nabla^E$ and $\nabla^F$, you can define a connection $\nabla$ on $E\otimes F$ by the formula
$$\nabla_X (e\otimes f) = \nabla^E_X e \otimes f + e \otimes \nabla^F_X f\ .$$
Using this you can extend $\nabla$ to all $\mathcal T(M)^{(k,l)}$ .