Vector Potential for Magnetic field when the field is not in simply-connected region

You ask

if the region where the field is defined has holes in it, what happens?

Well, in that case you can define the vector potential on simply-connected sub-regions $R_i$ whose intersection is the whole non-simply connected region $R$ and such that they differ by only by a gauge transformation on the regions of overlap. This is a physically well-motivated thing to do, because it means that up to gauge transformation, the vector potential can be defined on $R$.

Here's a simple example. Let $\ell=\{(x,y,z)\,|\, x=0, y=0\}$ denote the $z$-axis, then the region $R=\mathbb R^2\setminus\ell$ is not simply connected. To see this, simply consider a closed loop enclosing the axis; there is no way to continuously shrink it down to a point while staying in $R$. Because of this, the there is no $\mathbf A$ defined on all of $R$. However, let $\ell_+$ denote the positive $z$-axis, and let $\ell_-$ denote the negative $z$-axis, then the regions $R_- = \mathbb R^3\setminus \ell_+$ and $R_+ = \mathbb R^3\setminus \ell_-$ have the property that they are each simply connected and $R = R_+\cap R_-$. Moreover, we can define a vector potential $\mathbf A_+$ on $R_+$ and $\mathbf A_-$ on $R_-$ such that there exists a scalar function $\Lambda$ for which \begin{align} \mathbf A_+(\mathbf x) - \mathbf A_-(\mathbf x) = \nabla\Lambda(\mathbf x), \qquad \text{for all $\mathbf x\in R$} \end{align} In fact, here are the explicit expressions in spherical coordinates $(r,\theta,\phi)$: \begin{align} \mathbf A_{\pm} &= -g\frac{\cos\theta\mp 1}{r\sin\theta}\hat{\boldsymbol \phi} \end{align} I'll leave it to you to determine $\Lambda$; it's a fun exercise.

what are the physical consequences of that?

Well, in the context of quantum mechanics, these sorts of topological issues are physically relevant (I am unsure if there are examples in which they are relevant at the classical level, but I don't think so). I won't go into the details here (unless perhaps there is some demand), but the very vector potentials I wrote down in the example above come up when discussing magnetic monopoles and the quantization of electric charge (see Dirac quantization).

These topological issues also become significant in discussing the famous Aharonov-Bohm effect.