Does there always exist an irreducible representation occurring with multiplicity one when inducing from a closed subgroup to a compact Lie group?

Let $K=SU(2)$, $M=Z(SU(2)) = \{\pm I\}$, and $\tau$ the sign representation of $M$. Then given an irreducible representation $\sigma$ of $SU(2)$, $\sigma|_M$ is necessarily a character with multiplicity $dim(V)$. Moreover, the sign character appears exactly for the even dimensional representations (i.e. those of odd highest weight). Thus $\tau$ always appears with even multiplicity in any irreducible representation.

Regarding your motivation, those particular pairs of groups are special - I think the key word here is Gelfand pair.