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 a closed $n$-form under the integral sign, and $\partial_\mu A^\mu \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 a closed $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 generic connection rather than the Levi-Civita connection, our $n$-form is not closed, and the argument fails because the Stokes theorem does not apply anymore. Apologies for not noticing this in the earlier version of my reply.