Using the properties of circulant matrices, it can be shown that the solution space of the homogeneous system $(y_k=0\;\forall k\in\{1,\ldots,n\})$ is one-dimensional if $n\equiv 2\pmod 4$ and three-dimensional if $n\equiv 0\pmod 4.$
Note: You have to find the indices $j,\;0\leq j<n$ which satify
$$
x^3 + x^2 + x + 1 =0 \;\;\text{with}\;\;x=e^{2\pi ij/n}
$$
This is $j=\frac{n}{2}$ if $n\equiv 2\pmod 4$ and $j\in\left\{\frac{1n}{4},\frac{2n}{4},\frac{3n}{4}\right\}$ if $n\equiv 0\pmod 4.$
We can easily find vectors that span the solution space. If $n\equiv 2\pmod 4$, then
$$
w=(1, -1, 1, -1, \ldots , 1,-1)^T
$$
does the job.
If $n\equiv 0\pmod 4$, then we can use
$$
v_1 = (1,-1,0,0,1,-1,0,0,\ldots , 1,-1,0,0)^T \\
v_2 = (0,1,-1,0,0,1,-1,0,\ldots , 0,1,-1,0)^T \\
v_3 = (0,0,1,-1,0,0,1,-1,\ldots , 0,0,1,-1)^T
$$
Those vectors can also be used to check if the system of linear equations is solvable. You must get $\sum_k w_ky_k = 0$ if $n\equiv 2\pmod 4$ and $\sum_k (v_1)_ky_k=\sum_k (v_2)_ky_k=\sum_k (v_3)_ky_k=0$ if $n\equiv 0\pmod 4.$ This last condition is exactly what you have already discovered yourself.
In short:
If $n\equiv 2\pmod 4$, then check $\sum_k w_ky_k = 0.$ If this is true, remove the last equation (it is redundant) and set $x_n=0$ (or any other value you like). Find the other $x_k$ by solving the remaining system of linear equations ($n-1$ equations and $n-1$ unknowns.) You get a particular solution $x_0,$ and the general solution is
$$
x=x_0+\lambda w,\;\lambda\in\mathbb{R}
$$
If $n\equiv 0\pmod 4$, then check $\sum_k (v_1)_ky_k=\sum_k (v_2)_ky_k=\sum_k (v_3)_ky_k=0.$ If this is true, remove the last three equations (they are redundant) and set $x_{n-2}=x_{n-1}=x_n=0$ (or any other values you like). Find the other $x_k$ by solving the remaining system of linear equations ($n-3$ equations and $n-3$ unknowns.) You get a particular solution $x_0,$ and the general solution is
$$
x=x_0+\lambda_1 v_1+\lambda_2 v_2+\lambda_3 v_3,\;\lambda_1,\lambda_2,\lambda_3\in\mathbb{R}
$$