A simple example where the answer is 'no' is when $M=\mathbb{RP}^2$ (with, say, the standard metric of Gauss curvature $K\equiv1$, though, in dimension $2$, only the conformal structure on $M$ matters in the definition of harmonic map).
There is no non-constant harmonic map $f:\mathbb{RP}^2\to S^2$ (when $S^2$ given the standard metric with $K\equiv1$). In particular, there is not one that has nonzero degree.
The reason is that such a map would lift to $\tilde f:S^2\to S^2$ as a non-constant harmonic map, and it is well-known that such a map would have to be either holomorphic or anti-holomorphic when $S^2$ is regarded as $\mathbb{CP}^1$, i.e., the Riemann sphere. Since $\mathbb{RP}^2$ is $\mathbb{CP}^1=S^2$ divided by the anti-holomorphic involution $[z,w]\to [-\bar w,\bar z]$, it would follow that the holomorphic mapping $\tilde f$ would have to satisfy $\tilde f\bigl([z,w]\bigr) =\tilde f\bigl([-\bar w,\bar z]\bigr)$, which would be impossible unless $\tilde f$ were constant.