$n$ can be any even integer larger than $2$.

We first consider the case when $n$ is odd. Let $(x_j, y_j)$, where $j = 1, 2, \dots, n$, be the vertices of the polygon in anticlockwise direction. WLOG assume $x_1 = y_1 = 0$. By using the homothety $(x_j, y_j) \mapsto \left(\frac{x_j}{d}, \frac{y_j}{d}\right)$, we may assume the greatest common divisor of $x_1, x_2, \dots, x_n, y_1, y_2, \dots, y_n$ is $1$. In particular, not all coordinates are even numbers.

Let $a_j = x_{j+1} - x_j$ and $b_j = y_{j+1} - y_j$ for $j = 1, 2, \dots, n$, where the indices are taken modulo $n$. It is given that $a_j^2 + b_j^2 = c$ for some constant $c$.

* If $c \equiv 0 \pmod{4}$, then both $a_j, b_j$ are even. Since $x_0, y_0$ are even, we easily deduce that all $x_j, y_j$ are even. This contradicts our assumption.
* If $c$ is odd, then $a_j + b_j \equiv 1 \pmod{2}$. Thus, we have
$$1 \equiv \sum_{j=1}^{n} (a_j + b_j) = \sum_{j=1}^{n} (x_{j+1} - x_j + y_{j+1} - y_j) = 0 \pmod{2},$$
which is a contradiction.
* If $c \equiv 2 \pmod{4}$, then $a_j, b_j$ are odd. Thus, we have
$$1 \equiv \sum_{j=1}^{n} a_j = \sum_{j=1}^{n} (x_{j+1} - x_j) = 0 \pmod{2},$$
which is a contradiction.

Therefore, it is impossible that $n$ is odd.

For even $n \ge 4$, we provide the following construction. The following quadrilaterals have the properties that each side has length $5$, and two of the sides are vertical.
* (type I) a square with vertices $(0,0), (5,0), (5,5), (0,5)$
* (type II) a rhombus with vertices $(0,0), (4,3), (4,8), (0,5)$
* (type III) a rhombus with vertices $(0,0), (4,-3), (4,2), (0,5)$

We can place $\frac{n}{2}-1$ copies of these quadrilaterals in the order types I, II, III, II, III, II, III, ... by translating them to the position such that the left edge of the next quadrilateral overlaps with the right edge of the previous one as shown. This gives an $n$-sided polygon whose every side has length $5$.