In C non esiste il tipo di dato "string", semplicemente le stringhe sono array di caratteri. Il "%s" nella stringa di formato serve semplicemente a dire a scanf che non gli hai passato semplicemente un puntatore ad un singolo char, ma ad un array di char, e quindi può inserire tutti i caratteri che legge nell'array che inizia all'area di memoria che gli hai passato.
Comunque, nel tuo caso la forma corretta era la prima, con una piccola correzione:
Lo spazio dopo %c fa sì che la scanf si "mangi" il ritorno a capo (e altro eventuale whitespace) invece di lasciarlo nel buffer. Questo normalmente non è necessario (la scanf di base salta implicitamente spazi e ritorni a capi), ma %c acquisisce anche il whitespace.codice:scanf("%c ", &MAT[i][j]);
Con %s funzionava perché gli stavi facendo considerare ogni elemento come inizio di una stringa; inserendo da tastiera un solo carattere, scanf lo depositava nel primo elemento della stringa (ovvero, l'elemento di matrice passato) seguito dal carattere terminatore (il \0), che però veniva sovrascritto al momento di scrivere l'elemento successivo (nota che qui il whitespace veniva ignorato, solo %c non lo ignora).
Complessivamente andava, ma avevi sicuramente un piccolo buffer overflow (l'ultimo terminatore letto finiva fuori dall'array) e la potenzialità per un grande buffer overflow (se l'utente inseriva più di un carattere).