The smallest possible degree is $2n$. In what follows, we will frequently write $A_i = (x_i, y_i)$, and abbreviate $P(x_1, y_1, \dots, x_{2n}, y_{2n})$ to $P(A_1, \dots, A_{2n})$ or as a function of any $2n$ points.

Suppose that $f$ is valid. First, we note a key property:

**Claim (Sign of $f$).** $f$ attains either only nonnegative values, or only nonpositive values.
Proof. This follows from the fact that the zero-set of $f$ is very sparse: if $f$ takes on a positive and a negative value, we can move $A_1, \dots, A_{2n}$ from the negative value to the positive value without ever having them form a regular $2n$-gon — a contradiction.

The strategy for showing $\deg f \ge 2n$ is the following. We will animate the points $A_1, \dots, A_{2n}$ linearly in a variable $t$; then $g(t) = f(A_1, \dots, A_{2n})$ will have degree at most $\deg f$ (assuming it is not zero). The claim above then establishes that any root of $g$ must be a multiple root, so if we can show that there are at least $n$ roots, we will have shown $\deg g \ge 2n$, and so $\deg f \ge 2n$.
Geometrically, our goal is to exhibit $2n$ linearly moving points so that they form a regular $2n$-gon a total of $n$ times, but not always form one.
We will do this as follows. Draw $n$ mirrors through the origin, as lines making angles of $\frac{\pi}{n}$ with each other. Then, any point $P$ has a total of $2n$ reflections in the mirrors, as shown below for $n = 5$. (Some of these reflections may overlap.)
Draw the $n$ angle bisectors of adjacent mirrors. Observe that the reflections of $P$ form a regular $2n$-gon if and only if $P$ lies on one of the bisectors.
We will animate $P$ on any line $\ell$ which intersects all $n$ bisectors (but does not pass through the origin), and let $P_1, \dots, P_{2n}$ be its reflections. Clearly, these are also all linearly animated, and because of the reasons above, they will form a regular $2n$-gon exactly $n$ times, when $\ell$ meets each bisector. So this establishes $\deg f \ge 2n$ for the reasons described previously.

Now we pass to constructing a polynomial $f$ of degree $2n$ having the desired property. First of all, we will instead find a polynomial $g$ which has this property, but only when points with sum zero are input. This still solves the problem, because then we can choose
$$f(A_1, A_2, \dots, A_{2n}) = g(A_1 - \bar{A}, \dots, A_{2n} - \bar{A}),$$
where $\bar{A}$ is the centroid of $A_1, \dots, A_{2n}$. This has the upshot that we can now always assume $A_1 + \dots + A_{2n} = 0$, which will simplify the ensuing discussion.

We will now construct a suitable $g$ as a sum of squares. This means that, if we write $g = g_1^2 + g_2^2 + \cdots + g_m^2$, then $g = 0$ if and only if $g_1 = \cdots = g_m = 0$, and that if their degrees are $d_1, \dots, d_m$, then $g$ has degree at most $2 \max(d_1, \dots, d_m)$.
Thus, it is sufficient to exhibit several polynomials, all of degree at most $n$, such that $2n$ points with zero sum are the vertices of a regular $2n$-gon if and only if the polynomials are all zero at those points.

First, we will impose the constraints that all $|A_i|^2 = x_i^2 + y_i^2$ are equal. This uses multiple degree 2 constraints.
Now, we may assume that the points $A_1, \dots, A_{2n}$ all lie on a circle with centre 0, and $A_1 + \dots + A_{2n} = 0$. If this circle has radius 0, then all $A_i$ coincide, and we may ignore this case.
Otherwise, the circle has positive radius. We will use the following lemma.

Lemma. Suppose that $a_1, \dots, a_{2n}$ are complex numbers of the same non-zero magnitude, and suppose that $a_1^k + \dots + a_{2n}^k = 0$, $k = 1, \dots, n$. Then $a_1, \dots, a_{2n}$ form a regular $2n$-gon centred at the origin. (Conversely, this is easily seen to be sufficient.)
Proof. Since all the hypotheses are homogenous, we may assume (mostly for convenience) that $a_1, \dots, a_{2n}$ lie on the unit circle. By Newton's sums, the $k$-th symmetric sums of $a_1, \dots, a_{2n}$ are all zero for $k$ in the range $1, \dots, n$.
Taking conjugates yields $a_1^{-k} + \dots + a_{2n}^{-k} = 0$, $k = 1, \dots, n$. Thus, we can repeat the above logic to obtain that the $k$-th symmetric sums of $a_1^{-1}, \dots, a_{2n}^{-1}$ are also all zero for $k = 1, \dots, n$. However, these are simply the $(2n-k)$-th symmetric sums of $a_1, \dots, a_{2n}$ (divided by $a_1 \cdots a_{2n}$), so the first $2n-1$ symmetric sums of $a_1, \dots, a_{2n}$ are all zero. This implies that $a_1, \dots, a_{2n}$ form a regular $2n$-gon centred at the origin.

We will encode all of these constraints into our polynomial. More explicitly, write $a_r = x_r + y_r i$; then the constraint $a_1^k + \dots + a_{2n}^k = 0$ can be expressed as $p_k + q_k i = 0$, where $p_k$ and $q_k$ are real polynomials in the coordinates. To incorporate this, simply impose the constraints $p_k = 0$ and $q_k = 0$; these are conditions of degree $k \le n$, so their squares are all of degree at most $2n$.
To recap, taking the sum of squares of all of these constraints gives a polynomial $f$ of degree at most $2n$ which works whenever $A_1 + \dots + A_{2n} = 0$. Finally, the centroid-shifting trick gives a polynomial which works in general, as wanted.

Remark 1. Here is a more detailed approach of the mirror-reflection argument. Let $re^{i\theta}$ be the polar representation of the point $P$. The polar representations of its mirrored images are then
$$re^{i\theta}, re^{-i\theta}, re^{i(\frac{2\pi}{n}+\theta)}, re^{i(\frac{2\pi}{n}-\theta)}, \dots, re^{i(\frac{2(n-1)\pi}{n}+\theta)}, re^{i(\frac{2(n-1)\pi}{n}-\theta)}.$$
Clearly, they are all linear with respect to $P$ and lie on the circle of radius $r$ centred at the origin. As listed above, the $2n$ images are not necessarily in circular order around the circle. For convenience, assume $0 \le \theta \le \frac{\pi}{n}$, so the list now displays them in circular order. These images form the vertices of a regular $2n$-gon if and only if the angle between every two consecutive terms in the list (read circularly) is $\frac{\pi}{n}$. This is clearly the case if and only if $\theta = \frac{\pi}{2n}$. Consequently, the images are the vertices of a regular $2n$-gon if and only if $P$ lies on the internal bisector of the angle formed by some pair of consecutive mirrors.

Remark 2. We sketch here some versions of the arguments in the solution above.
To show that $\deg f \ge 2n$, we use the same constancy of sign claim and the convention that the polynomial is a function of points (= pairs of coordinates) $A_1, A_2, \dots, A_{2n}$. Assume that the values of $f$ are all non-negative.
Write $B(\varphi) = (\cos \varphi, \sin \varphi)$. Choose a substitution
$$A_{2i-1} = B\left((2i-1)\frac{\pi}{n} + \varphi\right) \quad \text{and} \quad A_{2i} = B\left(2i\frac{\pi}{n} - \varphi\right), \quad i = 1, 2, \dots, n.$$
Notice that the coordinates of the points $A_1, A_2, \dots, A_{2n}$ are all linear functions in $c = \cos \varphi$ and $s = \sin \varphi$, so, substituting these expressions into $f$, we get a polynomial $g(c, s)$ with $\deg g \le \deg f$.
Now, the values of $g$ are all non-negative (each being one of $f$), and, on the circle $c^2 + s^2 = 1$, it vanishes at exactly $2n$ points, namely, $(c, s) = (\cos \frac{\pi}{n}k, \sin \frac{\pi}{n}k)$, $k = 1, \dots, 2n$. We show that these properties already yield $\deg g \ge 2n$.
Obviously, if $g(c, s)$ possesses the properties listed above, then so does $g(c, -s)$, and hence so does $\bar{g}(c, s) = g(c, s) + g(c, -s)$.
The polynomial $\bar{g}$ is even in $s$, so it in fact depends only on $s^2$, and we may plug $s^2 = 1 - c^2$ into it, to obtain a polynomial $h(c)$ with $\deg h \le \deg g$ which is non-negative on $[-1, 1]$ and vanishes on this segment exactly at $c = \cos \frac{\pi}{n}k$. These are $n+1$ such points, and, except $c = \pm 1$, they should all be roots of $h$ of even multiplicity, due to sign conservation. All in all, this provides $2n$ roots of $h$, counted with multiplicity, hence $\deg f \ge \deg g \ge \deg h \ge 2n$, as desired.

For a bit alternative construction of a suitable $f$, one may notice that the Lemma in the above solution can be changed to impose vanishing of the elementary symmetric polynomials $\sigma_i(a_1, a_2, \dots, a_{2n})$, $i = 1, 2, \dots, n$, instead of Newton sums. Indeed, if the $\sigma_i$ all vanish, then so do the polynomials
$$\sigma_i(\bar{a}_1, a_2, \dots, \bar{a}_{2n}) = \frac{|a_1|^{2i} \sigma_{2n-i}(a_1, a_2, \dots, a_{2n})}{\bar{a}_1 \bar{a}_2 \dots \bar{a}_{2n}},$$
so $\sigma_i(a_1, \dots, a_{2n})$ also vanishes for $i = n+1, \dots, 2n-1$. Hence $a_1, a_2, \dots, a_{2n}$ are the roots of $z^{2n} - |a_1|^n$, as desired.