In a few words, it's because the vector potential is a polar vector, so it can't depend on the right hand rule. But if you give it a $\varphi$ component you have to pick one direction or the other, and the right hand rule is the only thing that can give you a preferred direction.
More explicitly, being a polar vector means that it changes sign under inversion of the coordinates. Under an inversion, the point $M$ goes to its antipodal opposite, and the dipole flips around. You can then reverse that with a 180º rotation, bringing the point $M$ back to its original position, rotating $\mathbf{A}$ with it, and making the dipole point upwards again. Since the source (the dipole) is back where it was at first, the potential must be the same. But if $\mathbf{A}$ points in the $\varphi$ direction, it will flip around after this inversion-rotation process! The only way out is for $A_\varphi$ to be zero. And note that this doesn't apply to any $r$ or $\theta$ components: they stay the same after inverting and rotating.
The fact that the vector potential is a polar vector is crucial. The magnetic field is an axial vector, and if instead of a dipole you had a small piece of current, you could certainly have a $B_\varphi$ component. In fact that's all you can have: the above argument implies that we must have $B_r = B_\theta = 0$.
Why is $\mathbf{A}$ a polar vector and $\mathbf{B}$ an axial vector (or pseudovector)? Let's start from the basics: the position vector $\mathbf{r}$ of a particle is a vector (i.e. polar vector) basically by definition, so the velocity, acceleration and hence force are also vectors. Also, here comes the crucial point: given two vectors $\mathbf{a}$ and $\mathbf{b}$, their cross product $\mathbf{a}\times\mathbf{b}$ is a pseudovector. You can verify this explicitly by just looking at what happens to everything under an inversion of the coordinates, but the deep reason is the right hand rule: it changes to a left hand rule after inversion. Similarly, the cross product of a vector and a pseudovector is a vector, and the cross product of two pseudovectors is a pseudovector.
In short: a pseudovector depends on the right hand rule, a vector doesn't. Applying the right hand rule an even number of times gives you something that doesn't depend on it.
Now look at the Lorentz force
$$\mathbf{F} = q \mathbf{v} \times \mathbf{B}.$$
Since $\mathbf{F}$ and $\mathbf{v}$ are vectors, $\mathbf{B}$ must be a pseudovector. But $\mathbf{B} = \nabla \times \mathbf{A}$, so $\mathbf{A}$ must be a vector. You just count the number of cross products.