For example, if I have a $4\times4$ magic square that looks like so:
\begin{pmatrix} \hspace{0.1ex}2 & 3 & \cdot & \cdot\hspace{1ex} \\ \hspace{0.1ex}4 & \cdot & \cdot & \cdot\hspace{1ex} \\ \hspace{0.1ex}\cdot & \cdot & \cdot & \cdot\hspace{1ex} \\ \hspace{0.1ex}\cdot & \cdot & \cdot & \cdot\hspace{1ex} \\ \end{pmatrix}
How can I determine if there exists a valid magic square for which these initial conditions hold?
In the present case, you can determine it by checking this list. There seems to be no such magic square.
In the general case, you can treat the emtpy squares as variables, introduce the $2n+2$ constraints and solve the corresponding system of linear equations. If you prescribe $k$ squares, this will leave $n^2-k-(2n+2)$ variables to choose freely. You can assign all possible values to them and check whether any of them make the entries come out to form the set $\{1,\ldots,n^2\}$; if so, you've found a magic square of the desired form. In the present case, you'd have $4^2-3-(2\cdot4+2)=3$ free variables, and $4^2-3=13$ numbers left to choose, so you'd have $13\cdot12\cdot11=1716$ combinations to try; an easy task for a computer.