I think Graham's answer already gave most of what you need to prove that $4$ is the smallest possible. Let $V$ be the integral closure of $R$, $n$ be the embedding dimension of $R$, and $e=e(R)$ be the multiplicity.
Claim: If $R=k[[x_1,\cdots,x_n]]/I$ is Gorenstein and $n$ is at least $3$, then $\dim_k(V/R)\geq e$.
Proof: Let $m$ be the maximal ideal of $R$. As Graham pointed out, we have $e = \dim_k(V/mV)$. So:
$$\dim_k(V/R) =\dim_k(V/mR)-\dim_k(R/mR) \geq \dim_k(V/mV)-1=e-1$$
We need to rule out the equality. If equality happens, then one must have $mV=mR$. This shows that $m$ is the conductor of $R$. As you already knew, since $R$ is Gorenstein, one must then have $\dim_k(V/R)=\dim_k(R/m)=1$. The inequality now gives $e\leq 2$. Abhyankar's inequality (part 2 of Graham's answer) gives $n\leq 2$, so $R$ is planar, contradiction.
Now, one needs to show that for $R$ non-planar, $e\geq 4$. You could use part $3$ of Graham's answer, or arguing as follows: if $n\geq 4$ we are done by Abhyankar inequality. If $n=3$, a Gorenstein quotient of $k[[x,y,z]]$ must be a complete intersetion, and so $I=(f,g)$, each of minimal degree at least $2$ since $R$ is not planar, thus $e$ must be at least $4$.
By the way, one could construct a domain $R$ such that $\dim_k(V/R)=4$ as follows:
Take $R=k[[t^4,t^5,t^6]]$. The semigroup generated by $(4,5,6)$ is symmetric, so $R$ is Gorenstein. The Frobenius number is $7$, and $V/R$ is generated by $t,t^2,t^3,t^7$.
EDIT (references, per OP's request): Abhyankar inequality is standard, for example see Exercise 4.6.14 of Bruns-Herzog "Cohen-Macaulay rings", second edition (Link to the exact page). Or see exercise 11.10 of Huneke-Swanson book, also available for free here. Or Google "rings with minimal multiplicity".
(The original references are now available thanks to Graham, see his comment below)
As for $e=\dim_k(V/mV)$, I could not find a convenient reference, but here is a sketch of proof using the above reference: First, using the additivity and reduction formula (Theorem 11.2.4 of Huneke-Swanson) to reduce to the domain case. Assume that $R$ is now a complete domain, then $V=k[[t]]$, and $R$ is a subring of $V$. Let $x\in m$ be an element with smallest minimal degree. Then $mV=xV$ ($V$ is a DVR), and it is not hard to see that $e=$ the minimal degree of $x$ $=\lambda(V/xV)$ (see Exercise 4.6.18 of Bruns-Herzog, same page as the link above).
Alternatively, one can use the fact that:
$$e(m,V) = \text{rank}_RV.e(m,R) = e $$
The second inequality is because $V$ is birational to $R$ so $\text{rank}_RV=1$. The left hand side can be easily computed by definition to be length of $V/xV$, which equals $\dim_k(V/mV)$. (use $m^nV=x^nV$ since $V$ is a DVR)
Fun exercise!