This text uses that N is a PSD matrix (see comments)
Let $\vec y$ be the vector $\vec x$ without the first element.
By direct summation:
$$\vec{x}^TM\vec{x} = 2 x_1 \sum_{i=2}^N x_i q_i + \vec y^T N \vec y
$$
Now for $\vec q = \vec 0$ this is PSD. Conversely, if $\vec q \ne \vec 0$, then you can always find a $\vec x$ for which it is not PSD. If $q_2 \ne 0$ (otherwise choose any other nonzero element of $\vec q$), then choose $x_i = 0$ for $i=3 \cdots N$ and $x_1 \ne0$, $x_2 \ne 0$. This gives
$\vec{x}^TM\vec{x} = 2 x_1 x_2 q_2 + (x_2, 0, \cdots ,0)^TN(x_2, 0, \cdots ,0)
$. Since N is PSD, we have $(x_2, 0, \cdots ,0)^TN(x_2, 0, \cdots ,0) = R \ge 0$.
If $R=0$, you select $x_1 = -x_2 q_2$ which makes the expression negative.
If $R>0$, you select $x_1 = -x_2 q_2 R /(q_2^2 x_2^2)$ which also makes the expression negative.
So you can always construct cases for $\vec q \ne \vec 0$ which violate the PSD condition.
So you need $\vec q = \vec 0$ to obtain PSD.
If $A + A^\top = B + B^\top$, then $A - B = -(A - B)^\top$. That is, the difference between the two matrices is an anti-symmetric matrix $M$, i.e. satisfying $M = -M^\top$. And, adding any such matrix $M$ to $A$ will make
$$(A + M) + (A + M)^\top = A + M + A^\top + M^\top = A + A^\top - M^\top + M^\top = A + A^\top.$$
That is, once we find a particular solution to $A + A^\top = P$, where $P$ is a fixed PSD matrix, then the remaining solutions will differ by an anti-symmetric matrix $M$. Taking the easy solution $A = P/2$, we see the solutions are:
$$\left\{\frac{P}{2} + M : M = -M^\top\right\}.$$
All this should make sense if you've studied linear equations. The map $A \mapsto A + A^\top$ is linear, making $A + A^\top = P$ a non-homogeneous linear equation. The solution is formed by taking a particular solution $P/2$ and adding the nullspace of the linear map, which are all these $M$ matrices.
Also, we could take the particular solution to be a triangular matrix, which affirmatively answers your question in the comments. However, if we take the particular solution to be $P/2$, we have the advantage that we only require $M \neq 0$, and we will definitely get a non-symmetric (and hence not PSD) matrix! This is because,
\begin{align}
\left(\frac{P}{2} + M\right)^\top = \frac{P}{2} + M &\iff \frac{P^\top}{2} + M^\top = \frac{P}{2} + M \\
&\iff \frac{P}{2} + M^\top = \frac{P}{2} + M \\
&\iff M^\top = M \\
&\iff M^\top = -M^\top \\
&\iff 2M^\top = 0 \\
&\iff M = 0.
\end{align}
Best Answer
By definition, $M$ is PSD, hence $$ \begin{bmatrix}x\\y\end{bmatrix}^TM\begin{bmatrix}x\\y\end{bmatrix}= \alpha x^2+2x\cdot q^Ty+y^TNy\ge 0,\qquad\forall x,y\tag{*} $$ Complete the squares in (*) $$ \alpha\left(x+\frac{1}{\alpha}q^Ty\right)^2+y^T\left(N-\frac{1}{\alpha}qq^T\right)y\ge 0,\qquad\forall x,y. $$ Take $x=-\frac{1}{\alpha}q^Ty$ to get $$ y^T\left(N-\frac{1}{\alpha}qq^T\right)y\ge 0,\qquad\forall y. $$