OK, now that I have read your questions more carefully, here is some more
preliminary information. Your Reed-Solomon code has a generator polynomial
of degree $4$ which is not the same as what you call the generator
polynomial, viz., $p(x) = x^3 + x + 1$. In coding theory $p(x)$
would be called the irreducible polynomial used to construct the field.
In this instance, it would more likely be called the primitive
polynomial since its root $a$ is a primitive element of the field, meaning
that all $7$ nonzero elements of the field can be represented as powers of
$a$.
So, what is this generator polynomial (call it $g(x)$) of the Reed-Solomon code?
You might have been given this information as part of the problem, so
look for it. The generator polynomial of a $t$-error-correcting Reed-Solomon
code has the property that $2t$ successive powers of $a$ are roots of
the polynomial. Thus, we have
$$\begin{align*}
g(x) &= (x-a^i)(x-a^{i+1})(x-a^{i+2}\cdots(x-a^{i+2t-1})\\
&= g_{2t}x^{2t} + g_{2t-1}x^{2t-1} + \cdots + g_1 x + g_0
\end{align*}$$
where all the coefficients $g_j$ are necessarily nonzero. Popular
choices for $i$ are $0$ and $1$, but unless you know $g(x)$, it
is not possible to answer the question about which
vectors are valid codewords, except possibly in the general
form "This vector is not a valid codeword for any choice
of $i$, $0 \leq i \leq 6$" which would require a lot more
calculation of the form given below.
Valid codeword polynomials are divisible by the generator polynomial
$g(x)$. So, if you are given the second form of $g(x)$ as
described above, then divide the alleged codeword polynomial
$c(x)$ (which,
for the vector $(c_0, c_1, \ldots, c_6)$,
could be $c(x) = c_0 + c_1x + \cdots + c_6x^6$ or
$c(x) = c_0x^6 + c_1x^5 + \cdots + c_5x + c_6$
depending on the convention used in the document
you are reading) by the generator polynomial $g(x)$ which is given
to you. This is plain polynomial long division as you would
have learned in secondary school except
that you are working over a finite field instead of real numbers. If the remainder is zero, the vector is indeed a codeword; if the remainder is nonzero, it is not a codeword.
On the other hand, if you are given the $4$ roots of $g(x)$ but not the
coefficients $g_j$, then rather than
multiplying out the four factors to get the $g_j$ and then doing
the polynomial division, it is easier to simply
evaluate the alleged codeword polynomial $c(x)$
at the four roots of the generator polynomial (this is called computing the syndrome in
coding theory). If all four evaluations $c(a^i)$, $c(a^{i+1})$,
$c(a^{i+2})$, $c(a^{i+3})$
result in $0$, $c(x)$ is indeed a valid codeword polynomial;
if at at least one evaluation gives a nonzero result, $c(x)$
is not a valid codeword polynomial.
This way of checking can be adapted to determine whether the vector in question
is a codeword in any double-error-correcting Reed-Solomon code. Evaluate
the codeword polynomial at $a^i$ for all $i, 0 \leq i \leq 6$. This is
computing the finite-field discrete Fourier transform which you
mentioned. Then look for $4$ consecutive $0$ values in the sequence
$$c(1), c(a), c(a^2), c(a^3), c(a^4), c(a^5), c(a^6), c(1), c(a), c(a^2).$$
If there are $4$ consecutive $0$ values beginning with $c(a^i), 0 \leq i \leq 6$,
then $c(x)$ is a valid codeword polynomial in the double-error-correcting
Reed-Solomon code with generator polynomial
$$g(x) = (x-a^i)(x-a^{i+1})(x-a^{i+2})(x-a^{i+3}).$$
There may be more than one choice of $i$ for which this holds.
On the other hand, there might not be $4$ consecutive zeroes in which
case you have shown that
$c(x)$ is not a valid codeword polynomial in any double-error-correcting
Reed-Solomon code of length $7$ over the finite field of $8$ elements.
Finally, your question about creating a list of codewords has the
following answer. The codewords are all the multiples of $g(x)$.
So, write out all the $8^3$ polynomials $b(x)$ of degree $2$ or less
(remember that polynomials of degree $2$ have $3$ coefficients, and we
have $8$ choices for each coefficient. The codewords then are
the $8^3$ polynomials $b(x)g(x)$. An easier way is to create
three vectors of length $7$ corresponding to $g(x)$, $xg(x)$ and
$x^2g(x)$ respectively, and then take all possible linear
combinations $b_2(x^2g(x)) + b_1 (xg(x)) + b_0g(x)$.
The parameters don't add up. Your $G$ generates a code of length 4 and rank 3, so its parity check matrix will have a single row ($4-3=1$).
The paper that you link to prescribes the use of a code of length $n=3t+1$ and rank $k=t+1$, so this won't fit into that scheme. If you intended $t=2$, then the code must have length $n=3t+1=7$.
Anyway, your $G$ is row equivalent to the reduced row echelon form
$$
\left(\begin{array}{cccc}
1&0&0&1\\
0&1&0&8\\
0&0&1&3
\end{array}\right),
$$
which gives us the check matrix
$$
H=\left(\begin{array}{cccc}
-1&-8&-3&1
\end{array}\right)=\left(\begin{array}{cccc}
-1&3&-3&1
\end{array}\right).
$$
Here I used a general recipe that a code generated by $G=(I|A)$ has check matrix
$H=(-A^T|I)$. For Reed-Solomon codes there are useful duality results that allow us to write a check matrix in many a form.
Best Answer
Why would you need to divide? You already know its structure as well as you know $g$'s:
It's equal to $(x-1)(x-5)(x-7)(x-9)(x-10)(x-11)(x-12)$
After you have this, you can use its corresponding word, then do cyclic shifts to find the rest of the parity matrix.