[[escafandra]]

En tu bucle principal pides palabras sin haber seresvado el espacio para todas elles y "peta"

Mira esta modificación a tu código respetando más o menos su estructura:

Código PHP:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define LARGOMAX 21

// Llena la matriz con caracteres /0
void inicializa(char **m, int filas, int columnas) {
    int i, j;

    for (i = 0; i < filas; i++)
        for (j = 0; j < columnas; j++)
            m[i][j] = '\0';
}

void PedirPalabras(char **palabras, int nPalabras){
   int i,x;

   for (i = 0; i < nPalabras; i++){
      printf("Introduce una palabra: ");
      scanf("%s", palabras[i]);
      for (x = 0; x < strlen(palabras[i]); x++){
         palabras[i][x]=toupper(palabras[i][x]);
      }
   }
}

// Llena los espacios vacíos con caracteres al azar
void rellena(char **m, int filas, int columnas) {
    int i, j;

    for (i = 0; i < filas; i++)
        for (j = 0; j < columnas; j++)
            if (m[i][j] == '\0')
                m[i][j] = rand() % 26 + 65;
}

// Muestra la sopa de letras
void muestra(char **m, int filas, int columnas) {
    int i, j;

    printf("\n\n");
    for (i = 0; i < filas; i++) {
        for (j = 0; j < columnas; j++)
            printf("%c ", m[i][j]);
        printf("\n");
    }
}

// Valida que la palabra s se pueda agregar a la matriz m
// en la posición (x, y) y en la dirección (dx, dy)
int valida(char **m, int filas, int columnas, const char *s, int x, int y, int dx, int dy) {
    int i, v = 1;

    for (i = 0; i < (int)strlen(s); i++, x += dx, y += dy){
        if (x < 0 || y < 0 || x >= columnas || y >= filas || (m[y][x] != s[i] && m[y][x] != '\0')){
            v = 0;
            break;
        }
    }
    if(v==1)
      printf("\n%s puede agregarse (x%d, y%d, dx%d, dy%d): %d", s, x, y, dx, dy, v);

    return v;
}

// Agrega la palabra s a la sopa de letras
void agrega(char **m, int filas, int columnas, const char *s) {
    int i, x, y, dx, dy;

    dx = rand() % 3 - 1;
    dy = rand() % 3 - 1;
    dx = dx == 0 ? 1 : dx;
    while (!valida(m, filas, columnas, s, x = rand() % columnas, y = rand() % filas, dx, dy)) ;
    for (i = 0; i < (int)strlen(s); i++, x += dx, y += dy)
        m[y][x] = s[i];
}

int main() {
    // Las palabras que se van a agregar a la sopa de letras
    // Deben ser tantas palabras como la definción de PAL
    // Escritas en mayúsculas para que se vean bien
    char **m, **palabras;
    int i;
    int filas, columnas, nPalabras;
    srand(time(0));

    printf("Introduce el numero de caracteres horizontales: ");
    scanf("%d",&columnas);
    printf("Introduce el numero de caracteres verticales: ");
    scanf("%d",&filas);

   bool Error = false;

   //Obtengo la memoria suficiente para el array que contendrá las palabras a colocar en sopa de letras
   printf("Introduce el numero de palabras a colocar: ");
   scanf("%d",&nPalabras);
   if(( palabras = (char**)malloc(nPalabras*sizeof(char*))) == NULL){
      Error != true;
   }else{
      for ( i = 0; i < nPalabras; i++ ){
        if(( palabras[i] = (char*)malloc(LARGOMAX+1)) == NULL )
           Error != true;
      }
    }


    //Obtengo la memoria suficiente para el array que contendrá la sopa de letras
    if (!Error && ( m = (char**)malloc(filas*sizeof(char*))) == NULL )
    {
      Error != true;
    }else{
      for (i = 0; i < filas; i++){
         if (( m[i] = (char*)malloc(columnas)) == NULL )
            Error != true;
      }
    }

    if(!Error){
      PedirPalabras(palabras, nPalabras);
      //Lleno la sopa de letra con \0's
      inicializa(m,filas,columnas);

      //Coloco las palabras en la sopa de letra
      for (i = 0; i < nPalabras; i++)
        agrega(m, filas, columnas, palabras[i]);

      //Muestro como quedan las palabras
      muestra(m, filas, columnas);
      getchar();

      //Relleno los huecos de la sopa de letra
      rellena(m, filas, columnas);
      getchar();

      //Muestro como queda la sopa de letra
      muestra(m, filas, columnas);
      getchar();
    }

    //Libero la memoria de la matriz de la sopa de letras
    if( m != NULL ){
      for ( i = 0; i < filas; i++ )
      {
         if (m[i] != NULL)
         {
            free(m[i]);
         }
      }
    }
    free(m);

    //Libero la memoria de la matriz de las palabras
    if( palabras != NULL ){
      for ( i = 0; i < nPalabras; i++ )
      {
         if (palabras[i] != NULL)
         {
            free(palabras[i]);
         }
      }
    }
    free(palabras);
    return 0;
} 


Saludos.