#Perl 5, 66 bytes

$n=pop;$_='#';for$x(0..$n){$_.=$"x($n-2).'#'};s/(.{$n})/$1\n/g;say 

Takes input as first command line argument.

Builds up a string of length n^2 with # at the proper spots, then inserts newlines at the right places.

Perl 5, 66 bytes

$n=pop;$_='#';for$x(0..$n){$_.=$"x($n-2).'#'};s/(.{$n})/$1\n/g;say 

Takes input as first command line argument.

Builds up a string of length n^2 with # at the proper spots, then inserts newlines at the right places.