Here it discusses primality (or more accurately irreducibility) and primitivity of polynomials in $G(2)$. More specifically it states that $x^6 + x + 1$ is irreducible and primitive.
But here I can divide $x^7 + 1$ by $x^6 + x + 1$ and get $x$ remainder $x^2+x+1$. Surely this means the the order of $x^6 + x + 1$ is at most $7$ and therefore nowhere near the required $2^6-1 = 63$ as required for primitivity.
What mistake am I making?
I guess it is my interpretation of
The order of a polynomial $f(x)$ for which $f(0)$ is not $0$ is the smallest integer $e$ for which $f(x)$ divides $x^e+1$. A polynomial over GF(2) is primitive if it has order $2^n-1$.
According to the definition in the first link you provided, to see that the order of $x^6+x+1$ is $2^6-1$, you only need to check that $(x^6+x+1)\nmid (x^{n}+1)$ for all $n<2^6-1$, and that $x^6+x+1$ does divide $x^{2^6-1}+1$. A computer check easily confirm that this is the case.
I don't see any reason why the division of $x^7+1$ by $x^6+x+1$, giving quotient x and remainder $x^2+x+1$, would imply that the order is at most $7$, as you claimed.