Make some Prime Squares!
05AB1E, 64 63 56 53 48 46 bytes

°ÅPIùćÐ4FˆθUKD.ΔθyXÅ?yXÅ¿)¯gè}ÐNĀiR}¦}I¯JŽ9¦SΛ


-1 byte thanks to @Mr.Xcoder
-5 bytes thanks to @Grimy.

Try it online. (Times out for \$n&gt;4\$. Here the slightly faster 53 bytes version which times out for \$n&gt;7\$ instead.)

Explanation:



°                 # Raise the (implicit) input to the power 10
 ÅP               # Get a list of primes within the range [2, n^10]
   Iù             # Only keep those of a length equal to the input
ć                 # Extract the head; push the remainder-list and first prime separately
 Ð                # Triplicate this first prime
4F                # Loop 4 times:
  ˆ               #  Add the (modified) prime at the top of the stack to the global array
  θU              #  Pop and store the last digit of the prime in variable `X`
  K               #  Remove this prime from the prime-list
  D               #  Duplicate the prime-list
   .Δ             #  Find the first prime `y` in the prime list which is truthy for:
     θ            #   Get the last digit of prime `y`
     yXÅ?         #   Check if prime `y` starts with variable `X`
     yXÅ¿         #   Check if prime `y` ends with variable `X`
     )            #   Wrap the three results above into a list
      ¯g          #   Get the amount of items in the global array
        è         #   And use it to index into these three checks
                  #   (Note that only 1 is truthy for 05AB1E, so the `θ` basically checks
                  #    if the last digit of prime `y` is 1)
    }Ð            #  Triplicate the found prime
      NĀi }       #  If the loop index is 1, 2, or 3:
         R        #   Reverse the found prime
      ¦           #  And then remove the first digit of the (potentially reversed) prime
}                 # After the loop:
 I                # Push the input as length
 ¯J               # Push the global array joined together to a single string
 Ž9¦S             # Push compressed integer 2460 converted to a list of digits: [2,4,6,0]
 Λ                # Draw the joined string in the directions [2,4,6,0] (aka [→,↓,←,↑])
                  # of a length equal to the input
                  # (which is output immediately and implicitly as result)


See this 05AB1E tip of mine (section How to compress large integers?) to understand why Ž9¦ is 2460. And see this 05AB1E tip of mine to understand how the square is output with the Λ Canvas builtin.

The relevant code for printing the Canvas in a square is: NĀiR}¦ and I¯JŽ9¦SΛ. Let's take n=4 as example. The primes it will find with the rest of the code are [1009,9001,1021,1031]. The first code-part mentioned in this paragraph will save them as this instead: [1009,"001","201","301"]. The second code part of this paragraph will then use the Canvas builtin Λ with options:
- \$a\$ (side-length) = I: the input
- \$b\$ (string to print) = ¯J: the global array joined together (so "1009001201301" for n=4)
- \$c\$ (direction) = Ž9¦S: the directions [2,4,6,0], which will be [→,↓,←,↑] respectively