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$.