Your stochastic domination condition can be rewritten as $$g(x):=P(X\le x)+P(X\le c-x)\ge1 \tag{1}\label{1}$$ for all real $x$.
If $c\ge2M$, then for all real $x$ $$g(x)\ge\max(P(X\le x),P(X\le c-x)) =P(X\le\max(x,c-x))\ge P(X\le c/2)\ge P(X\le M)=1,$$ so that \eqref{1} holds.
On the other hand, if $c<2M$ and $P(X=M)=1$, then $$g(c/2)=P(X\le c/2)=0,$$ so that \eqref{1} does not hold. (If you insist that the support of $X$ be the entire interval $[-M,M]$, just use an approximation.)
So, the best lower bound on $c$ under the given conditions is $2M$. (There is no finite upper bound on $c$.