A stronger property seems to hold: If $n$ fulfills the congruence condition such that $c(n)$ is expected to be a sum of $c(k)$'s with $k<n$, then the following greedy algorithm works (for both questions) up to $n=10000$: Start with $f=c(n)$. For $j$ running from $n-1$ down to $0$ replace $f$ with $f+c(j)$ whenever $f$ and $c(j)$ have the same degree. So the degree of the new $f$ drops in such a step. If we get $f=0$, then we have the requested sum. If we finish in $j=0$ and still $f\ne0$, then the algorithm fails.

A Sage code (for the second question) which checks the cases up to $n=10000$ within a few seconds is

A stronger property seems to hold: If $n$ fulfills the congruence condition such that $c(n)$ is expected to be a sum of $c(k)$'s with $k<n$, then the following greedy algorithm works (for both questions) up to $n=10000$: Start with $f=c(n)$. For $j$ running from $n-1$ down to $0$ replace $f$ with $f+c(j)$ whenever $f$ and $c(j)$ have the same degree. So the degree of the new $f$ drops in such a step. If we get $f=0$, then we have the requested sum. If we finish in $j=0$ and still $f\ne0$, then the algorithm fails.

A Sage code (for the second question) which checks the cases up to $n=10000$ within a few seconds is

K.<x> = GF(2)[]
l = [K(0), K(1), K(1), x, x^2, x^4+x^2+x]
n = len(l)
while n < 10001:
    f = l[-1] + (x^6+x^5+x^2+x)*l[-6]+x^(n-6)*(x+x^2)
    l.append(f)
    if n%6 in [0,2]:
        print n
        for j in range(n-1,0,-1):
            if f.degree() == l[j].degree():
                f += l[j]
                if f == 0:
                    break
        else:
            print "FAIL"
            break
    n += 1