Actually the property you mention
$p(x)$ of degree $n$ cannot be factored, and divides $x^k-1$ for the first time when $k=2^n-1$
means the polynomial $p(x)$ of degree $n$ is primitive. If $p(x)$ cannot be factored into a product of polynomials of lower degree then it is irreducible. It is enough to consider irreducible polynomials of lower degree (like prime numbers) as possible factors.
Therefore one could check whether $p(x)$ factors by methods similar to checking whether a number is prime. However, the following helps:
For $i ≥ 1$ the polynomial $x^{2^i}-x \in \mathbf{F}_2[x]$
is the product of all monic irreducible polynomials in $\mathbf{F}_2[x]$ whose degree divides $i$.
So, you could compute $x^{2^n}-x$ modulo $p(x)$ by the division algorithm and declare $p(x)$ irreducible if the answer is zero.