How to obtain the first definition from the second
Let $E$ be the bundle $\mathcal{J}^{r,s}$ and $F$ be the bundle $\Omega^1 \times \mathcal{J}^{r,s}$. The precise definition of $\mathcal{J}^{r,s}$ doesn't matter that much here, but for concreteness let's say it is the set of rank $(r,s)$ tensor fields over $M$ on which the metric inner product extends as $\langle\cdot,\cdot\rangle$. More precisely, if $\{e_i\}$ is a frame of orthonormal vectors and $\{f_i\}$ a frame of orthonormal covectors, we have, for $W,Z\in \Gamma(\mathcal{J}^{r,s})$
$$ \langle W, Z\rangle = \sum_{i_1, \ldots, i_r, j_1, \ldots, j_s = 1}^{\dim M} W(e_{i_1}, \ldots, e_{i_r}, f_{j_1} , \ldots, f_{j_s}) Z(e_{i_1}, \ldots, e_{i_r}, f_{j_1} , \ldots, f_{j_s}) $$
The inner product can be defined on $F$ (aka $\Omega^1 \times \mathcal{J}^{r,s}$) analogously.
Now, let $W \in \Gamma(\mathcal{J}^{r,s})$ and $Z\in \Gamma(\Omega^1 \times\mathcal{J}^{r,s})$, the definition requires $\nabla^*$ satisfies
$$ \int \langle \nabla W, Z \rangle ~\mathrm{dvol}_g = \int\langle W, \nabla^* Z\rangle ~\mathrm{dvol}_g \tag{1}$$
for any choice of $W$ and $Z$. Now, a direct computation using the metric compatibility of the inner product shows you that, if we write $P\in \Gamma(\Omega^1)$ as
$$ P(X) = \sum_{i_1, \ldots, i_r, j_1, \ldots, j_s = 1}^{\dim M} W(e_{i_1}, \ldots, e_{i_r}, f_{j_1} , \ldots, f_{j_s}) Z(X, e_{i_1}, \ldots, e_{i_r}, f_{j_1} , \ldots, f_{j_s}) $$
we have, by Leibniz rule,
$$ \sum_{e_i} (\nabla_{e_i} P)(e_i) = \langle \nabla W, Z\rangle - \langle W, \nabla^* Z \rangle \tag{2}\label{lb}$$
where $\nabla^*$ is defined as in your first definition. To conclude if suffices to observe that if $W, Z$ have compact support, the left hand side of \eqref{lb} integrates to 0 by the divergence theorem.
How to obtain the formula for the Laplacian
Directly compute using the first definition you have
$$ \nabla^* \circ \nabla W (\cdots)= - \mathrm{tr} \{ ((X,Y) \mapsto \nabla_X (\nabla W)(Y, \cdots) = \nabla^2_{X,Y} W(\cdots)\} $$