Y ¿qué tienes hecho hasta ahora?
Muestra lo que tienes hecho, para que tengamos una base con la que trabajar e indica la duda que tengas.

Está bien, pero debes retocar una cosa:
Cuando vas a inicializar las columnas, y, y una de estas inicializaciones falla retornas NULL y regresas, pero esto te crea pérdida de memoria: todos los punteros anteriormente inicializados desaparecerán al salir de la función, pero su memoria seguirá adquirida.

P.ej.: Si la última inicialización de y falla pedrerás la memoria del array principal, x, y de cada una de las ys, menos la última que ha fallado.

Bueno, tampoco habría tanta ventaja. El compilador de java pasa a bytecode de la máquina java el código y después la máquina java va traduciendo el código máquina de la máquina virtual al código máquina del procesador. Toda una historia muy larga. Y el trabajo este se realiza cada vez que se ejecuta un java. No sé si hace como .NET que traduce al momento y al mismo tiempo guarda en caché las instrucciones en IL para una próxima ejecución más rápida.
En cámbio C, normalmente, lo traduce todo a ensamblador y el linker a código máquina. Esto unido a que tiene un entorno de ejecución pequeño es lo que lo convierte en un lenguaje rápido, pero a la vez inseguro porque su entorno de ejecución hace muy poco para el programador.

Varias cosas:
En base a tu problema, cuándo encuentres el nombre, la siguiente lectura con fscanf te dará la siguiente línea del archivo, el teléfono.

Cuando se trata de recoger una cadena con un formato bien establecido de antemano, nada mejor que scanf o fscanf. La razón es que su cadena de configuración es muy configurable y discrimina muy bien los elementos a tomar.

Por otra parte, los caracteres de nueva línea que están al final de las cadenas.
fgets recoges el carácter de nueva linea, con scanf y fscanf no. Así que según que función uses debes lidiar de una forma u otra con este problema.

Aquí te lo expongo, para ver el efecto del carácter de nueva línea comenta las lineas con scanf y fscanf y descomenta las de fgets.

#include<stdio.h>
#include<string.h>
 
int main() {
    FILE *f;
    char nombre[20];
    char cadena[20];
    int encontrado = 0;
    f = fopen("archivo.txt", "r");
    if(!f) {
        printf("*** Archivo de datos no encontrado ***\n");
        return 1;
    }
    printf("> ");
    // fgets(nombre, 19, stdin);
    scanf("%19s", nombre); while(getchar() != '\n'); // <-- Mejor así. Los nombres no tiene caracteres de nueva linea :D
    do {
        // fgets(cadena, 19, f);
        fscanf(f, "%19s", cadena); fgetc(f);
        if(strcmp(cadena, nombre) == 0)
            encontrado = 1;
    } while(!feof(f) && !encontrado);
    if(encontrado) {
        printf("Nombre   : %s\n", nombre);
        // fgets(cadena, 19, f);
        fscanf(f, "%19s", cadena); fgetc(f);
        printf("Telefono : %s\n", cadena);
    }
    else printf("No se ha encontrado el registro.\n");
    fclose(f);    
    return 0;
}
 

Si le pasas el puntero a una función para que ésta le asigne un espacio en la memoria sí debes pasar la dirección del puntero como argumento (un puntero a puntero).

O puedes hacer una función que dentro de ella declare un puntero temporal y le asigne la memoria, después devuelves el puntero con el return y lo recoges en el main con una variable puntero.

Ah, ok, entonces sí 

No, pero tampoco son tan difíciles de hacer:
Con una libreta de hojas a cuadritos y un lápiz haz el dibujo de como debe ser el ahorcado.
A cada cuadro que tengas dibujado buscas un carácter imprimible (no hace falta que sean letras, en ASCII hay caracteres para dibujar) que más se asemeje a la forma del dibujo del cuadro.
En código creas una tabla de dimensiones iguales a los cuadros que han hecho los dibujos y metes esos caracteres dentro.
Después, durante el juego, vas pintando las porciones del ahorcado (metiendo el carácter dibujado o un carácter blanco) dependiendo del número de fallos del jugador.

Si lo haces pequeño puedes poner el dibujo en la parte de arriba de la ventana y el texto de juego abajo. Si ya te ves con corazón de hacerlo más complicado puedes poner el dibujo a la izquierda o a la derecha de la ventana teniendo en cuenta que la pantalla se va a pintar línea a línea, es decir:
deberás pintar la primera línea del dibujo y escribir la primera línea del texto del juego; pasar a la segunda línea de la ventana, dibujar la segunda línea del ahorcado y escribir la segunda línea del texto; y así ir repitiendo hasta terminar de pintar la pantalla.

No lo has entendido:
Usar fflush(stdin); es una muy mala práctica.

Usa sdl2 para el apartado gráfico, o algún ide que te permita fácilmente construir ventanas, o siempre pueded hacer un dibujito con caracteres.

La función while en este caso lo que hace es ir tomando caracteres del buffer del teclado y a cada repetición no hace nada, que es lo que marca el punto y coma.

La instrucción se irá repitiendo hasta que recoja el carácter '\n' (lo habrá sacado del buffer) y según la condición, como el carácter devuelto por getchar() será igual a '\n' se va a parar la repetición del while y el programa continuará con el buffer de teclado vacío.