For a magnetic field we can have different solutions of its vector potential. What is the physical aspect of this fact? I mean, why the nature allows us not to have an unique vector potential of a field?
There is no "physical aspect of this fact". The physical variables are the electric and the magnetic field, not the potentials. Introducing the potential is aesthetically and technically pleasing, but it is not necessary. A gauge symmetry is not a physical symmetry.
The reason you can have a non-unique potential is that every divergence-free field such as the magnetic field has a vector potential whose curl it is, but adding any gradient to that potential still gives the same magnetic field since the curl of a gradient is zero. The equation defining the magnetic vector potential is simply underdetermined.
Note that even the effect that is usually cited as showing the potentials being "physical", the Aharanov-Bohm effect, does not make the potential unique. The quantity that is relevant is the integral of the vector potential $A$ along a closed loop $\gamma$, and if we denote the region inside $\gamma$ as $U$, we have $\int_\gamma A = \int_U B$ by Stokes' theorem, so what really matters here is the flux through the loop, not the specific value of the potential. And one has to close the loop to observe a phase difference (or, well, maybe not always, but the phase is still only dependent on the flux, not on a gauge-variant potential value). In any case, this is a quantum effect. In the classical theory, the potential is definitely not "physical" in the sense of being measureable.