$\newcommand\ep\varepsilon$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)=2P(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. For instance, you can assume that $P(X\in B)=(1-\ep)\,1(M\in B)+\ep\dfrac{|B\cap[-M,M]|}{2M}$ for any $\ep\in(0,1/2]$ and all Borel subsets of $\Bbb R$. Then the support of the distribution of $X$ will be the entire interval $[-M,M]$, whereas $g(c/2)=2P(X\le c/2)=2\ep\dfrac{M+c/2}{2M}<1$ if $c<2M$.)

So, the best lower bound on $c$ under the given conditions is $2M$. (There is no finite upper bound on $c$.