Is it possible to construct a $3*3$ MDS matrix in $GF(2^4)$? I'm trying to construct a minimal MDS matrix for a toy cipher. I'm not entirely sure, how the various code parameters are tied to my block size, and how exactly is the binary matrix formed, when you have a generator polynomial.

I'm also having a hard time in understanding what's the smallest field and matrix size, where MDS makes sense.
A matrix $M$ of order $n$ is an MDS (Maximum Distance Separable) matrix if and only if every sub-matrix of $M$ is non-singular. Therefore, if you have an $n\times n$ MDS matrix $M$, constructing the $(n-1)\times (n-1)$ MDS matrix $M'$ is so easy. $M'$ can be constructed by choosing an arbitrary $(n-1)\times (n-1)$ sub-matrix of $M$. Here you can find some information about constructing the MDS matrices over $GF(2^q)$.