Is the space of connections modulo gauge equivalence paracompact?

Yes, the space of gauge orbits of connections is paracompact (even when you the use Fréchet topology).

First, the space of all connections is paracompact since it is an affine space modelled on a nuclear Fréchet space (and/or it is metrisable). Narasimhan & Ramadas (Geometry of SU(2) Gauge Fields) showed that the action of the group of gauge transformation is proper (they actually only consider SU(2) gauge theories over $S^3$ but their argument generalizes to arbitrary structure groups and arbitrary compact base manifolds). For proper group actions, the orbit space is Hausdorff and the canonical projection map is closed. Since the image of a paracompact Hausdorff space under a closed continuous map is also paracompact, we conclude that the orbit space is paracompact.

Moreover, the gauge orbit space is stratified by smooth (Fréchet) manifolds (it's the usual orbit type stratification, the top stratum being the space of irreducible connections, see for example The orbit space of the action of gauge transformation group on connections or On the gauge orbit space stratification: a review). Since every stratum is modelled on a nulear Fréchet space, they are even smoothly paracompact (see Convenient Setting of Global Analysis by Kriegl & Michor for further details, especially chapters 14 (Smooth Bump Functions) to 16 (Smooth Partitions of Unity and Smooth Normality)).

I assume that by Sobolev topology you mean the topology induced by the Sobolev norm. Since all normed spaces are metric spaces the affirmative answer to your question follows from the fact that all metric spaces are paracompact. See e.g. A new proof that metric spaces are paracompact by Mary Ellen Rudin (pdf).

edit

I missed that you are asking for connections modulo gauge equivalence. In that case I can refer you to Theorem 2 of arXiv:1012.3180 where it is proved* that the moduli space of all irreducible connections is locally Hausdorff Hilbert manifold and that the space of all irreducible connections forms a $\mathrm{Gau}$-principal bundle over it.

.* In the setting of Lie algebroids and their connections which subsume many classical cases.