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 $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 an $n$-form while in the second case it is, and that's that.
The above argument certainly works if $\nabla$ is the Levi-Civita connection for $g$. It also apparently remains valid even if it is not the case, essentially because $\nabla_\mu A^\mu$ is a 0-form anyway, no matter whether $\nabla$ is Levi--Civita, and what we have under the integral sign is the Hodge dual of this 0-form. On the other hand, $\partial_\mu A^\mu$ is not a 0-form because of the wrong transformation law, and things break down.