The second expression should be correct. The Stokes theorem per se does not "know" about covariant derivatives. However, the differential forms have certain transformation properties under the changes of local coordinates. To get the boundary term, you need an exact $n$-form under the integral sign, and $\left(\partial_\mu A^\mu\right) \sqrt{|g(x)|}$ just does not transform the right way (assuming that $A_\mu$ are components of a vector field), so in the first case the expression under the integral sign can't be an exact $n$-form while in the second case it is if $\nabla$ is the Levi-Civita connection for $g$, and that's that.
Namely, in the second case the integral can (up to an inessential constant factor) be rewritten as $$\int_M \partial_\mu \left(\sqrt{|g(x)|} A^\mu\right) \mathrm{d} x,$$ and you can use the Stokes theorem.
Important warning: If $\nabla$ is a completely generic connection rather than the Levi-Civita connection, our $n$-form is not exact, and the argument fails because the Stokes theorem does not apply anymore.
Now, if $\nabla$ is compatible with $g$ and ${}^g\nabla$ is the Levi-Civita connection for $g$, then $\nabla g$=0 and it can be shown that there exists a (1,2)-tensor field $T$ such that $$\nabla={}^g\nabla+T.$$.
In particular, we have $$\nabla_\mu A^\mu={}^g\nabla_\mu A^\mu+T_{\rho\nu}^\nu A^\rho.$$
While ${}^g\nabla_\mu A^\mu$ is proportional to $\partial_\mu \left(\sqrt{|g(x)|} A^\mu\right)$, and we can apply the Stokes theorem to see that the contribution of this term to the integral vanishes, we get $$\int_M \nabla_\mu A^\mu \sqrt{|g(x)|} \mathrm{d} x=\int_M T_{\rho\nu}^\nu A^\rho \sqrt{|g(x)|} \mathrm{d} x.$$
However, the algebraic conditions on $T$ that follow from compatibility of $\nabla$ with the metric $g$ appear to yield $T_{\rho\nu}^\nu=0$ (have no time to write this out in detail, sorry), so the above integral vanishes and the above arguments work even if $\nabla$ is just compatible with $g$. Apologies for not pointing this out in the earlier version of my answer.