$3$ is the least possible.
Ingredient 1: For a one-dimensional complete local ring $R$ with integral closure $\tilde R$, the $k$-dimension of $\tilde{R}/R$ is one less than the multiplicity $e(R)$ of the ring. This is because $e(R) = \dim_k (\tilde {R}/\mathfrak{m})$, which in turn is due to Greither in 1982.
Ingredient 2: There is an inequality due to Abhyankar for the multiplicity of a CM local ring: $$e(R) \geq \mu_R(\mathfrak{m}) - \dim R + 1$$ where $\mu$ denotes the minimal number of generators.
Ingredient 3: It's relatively easy to see that for a Gorenstein local ring that is not a hypersurface (e.g. a one-dimensional non-planar Gorenstein local ring) we can do one better than Abhyankar's bound. Namely, if we had equality in Abhyankar's bound, then $\mathfrak m^2 = \mathbf{x}\mathfrak m$ for some minimal reduction $\mathbf{x}$ of the maximal ideal. Count lengths in $\bar{R} = R/(\mathbf{x})$, remembering that it has one-dimensional socle since $R$ is Gorenstein, to see that $\dim R = \mu_R(\mathfrak m) -1$. Therefore we have $$e(R) \geq \mu_R(\mathfrak{m}) - \dim R + 2$$ for a Gorenstein non-hypersurface $R$.
Applying this formula with $\mu_R(\mathfrak m) \geq 3$ and $\dim R = 1$, we get that the multiplicity is at least $4$, so the degree is at least 3.
edit: oops, I goofed with the "one less than" part. The correct lower bound is $3$, not $4$. I believe you might have goofed too: isn't the multiplicity of your example 4, so the degree should be 3?