I understand that electrostatic potential is scalar because the curl of the field is zero, and this implies the electrostatic field is the gradient of the scalar potential to satisfy this. Similarly the divergence of a magnetostatic field is zero so a magnetostatic field is the curl of the vector potential.
But what actually determines when you would use which potential? Is it purely to do with these definitions in electro and magneto statics, or is it something else?
For some vector field $\mathbf F$, you can use a scalar potential (unique up to a constant) whenever $\nabla\times\mathbf F=0$, and you can use a vector potential (unique up to the gradient of a scalar field) whenever $\nabla\cdot\mathbf F=0$. These are purely mathematical ideas, but you can see how this (very usefully) applies to the specific cases of static electric and magnetic fields as you have explained in your question.
The good hint is in the scalar or vectorial properties of the sources.
For the magnetic field, the sources are currents, which are vectors since currents flows in specified direction: it’s no surprise the associated potential should be a vector.
For (time-independent) electric fields not induced by magnetic fields, the sources are charges, which are scalar (one only needs to specify the magnitude of the charge) so it’s no surprise the associated potential is a scalar.
Of course if you have induction, i.e. if the $\vec E$ is due to a changing $\vec B$, then $\vec E$ depends on the vector potential which is the source of $\vec B$.
From a more general point of view, the scalar potential and the vector potential are parts of the electromagnetic four-potential.
The four-potential is defined up to a gauge transformation. To answer your question, one uses the gauge that is the most convenient for the specific problem. For example, in the case of electrostatics one can find such a gauge that the vector potential vanishes and use the scalar potential. In a general case, this is not possible, but one can always use such a gauge that the scalar potential vanishes (Weyl gauge). Therefore, the vector potential is always sufficient for any electromagnetic problem, not just for magnetostatics (for example, one can use it for electrostatics as well), but it is not always convenient.
