Al usar una matriz bidimensional quiere decir que para guardar u obtener un dato ocupas indicarle la posicion y a como veo en el primer for solo colocas uno que enrealidad deberia ser

M[i ][j] = ' ';

Bueno ese es el error que veo en todo donde usas M, ya que pues solo le indicas una posicion mas no la segunda.

Hola! si bien hacer M[j]= ' '; no es el error logico del programa es un error de compilacion. Debe ser como dijo s00rk: M[i ][j] = ' ';

Tenes varios errores en el programa, uno de ellos esta en la condicion de los dos for: j<strlen(str)
Estas utilizando una condicion que no tiene nada que ver con lo que queres hacer. Tanto para ordenar como para imprimir deberias usar:
j<k
ya que k es el contador de tu programa que indica cuantas lineas ingresaste por consola

El algoritmo de ordenamiento esta mal; una pista deberias utilizar dos for

Tambien la impresion esta mal, solo basta con un for, y el formato del printf debe ser %s no %c

Arregla esas cosas si podes sino segui preguntando, Saludos

Lei mejor el comentario de soork y me equivoque en algo, no tenes que usar M[j]= ' '; en todo el programa sino solo en:

for(i=0;i<Maxanzahl;i++){
       for(j=0;j<Maxstrl;j++){
         M[i][j]= ' ';
       }
}

Tambien la impresion esta mal, solo basta con un for, y el formato del printf debe ser %s no %c

Te dejo el codigo funcionando:

#include <stdio.h>
#include <string.h>
#define Maxstrl 50
#define Maxanzahl 100
 
int main(){
 
  char x[Maxstrl]; // x no debe ser una matriz sino un array unidimensional
  char str[Maxstrl];
  char M[Maxanzahl][Maxstrl];
  int i,j,min,m,k=0;
 
  for(i=0;i<Maxanzahl;i++){
       for(j=0;j<Maxstrl;j++){
       M[i][j]= ' ';
       }
 
}
 
  while(fgets(str,Maxstrl,stdin)!=NULL){
    if(str[strlen(str)-1]=='\n'){
      str[strlen(str)-1]='\0';
      strcpy(M[k],str);
      k++;
    }
  }
 
  for(j=0;j<k-1;j++){
    for(m=0;m<k-j-1;m++){
       if(strcmp(M[m],M[m+1])>0){ // faltaba las llaves del if
      strcpy(x,M[m]);
      strcpy(M[m],M[m+1]);
      strcpy(M[m+1],x);
      }
    }
}
 
// esto tenias q hacer para la impresion
  for(i=0;i<k;i++){
      printf("%s\n",M[i]);
    }
 
  return 0;
 
}

Para entender mejor lo que hice en el ordenamiento busca algo como: "metodo de la burbuja en C" en ingles creo q es "booble-sort"

Saludos

si te sirve..
http://foro.elhacker.net/programacion_cc/ejemplo_de_ordenamientos_basicos-t358139.0.html