I've proven that, given a first-order $\phi$ in the language $\in$ and $v\in M^{<\omega}$, there is a first-order formula $\psi(M,v)$ that is equivalent to $\langle M,\in\rangle\models\phi(v)$. Specifically, this formula is simply $\phi(v)$ with all quantification over $M$. Although the paper is still being written, you may see the proof in the paper which I am writing here.
This brings up an interesting conjecture, which is the following:
Given a first-order sentence $\phi$ in the language $\{\in,c\}$ where $c$ is a constant symbol and some class $M$, $\langle M,\in,S\rangle\models\phi$ is equivalent to $M\models\psi(S)$ for some first-order $\psi$.
What is the proof of this conjecture? It seems intuitively true if one lets $\psi$ to be $\phi$ with $c$ replaced by the parameter of $\psi$.
Yes, just let $\psi$ be $\phi$ with every instance of the symbol $c$ replaced by some variable which does not occur in $\phi$. You can prove this by induction on formulas. More precisely, suppose $\phi(x_1,\dots,x_n)$ is a formula with free variables $x_1,\dots,x_n$, and let $\psi(x_1,\dots,x_n,y)$ be the formula obtained by replacing all instances of $c$ with a new variable $y$. Then by induction on $\phi$, you prove that for any $v_1,\dots,v_n\in M$, $\langle M,\in,S\rangle\vDash \phi(v_1,\dots,v_n)$ is equivalent to $\langle M,\in\rangle \vDash \psi(v_1,\dots,v_n,S)$.