The trivial method of checking primitivity would go as follows.
I am assuming that you know the factorization of $p^n-1$. Then you should check for each prime divisor $\ell$ of $p^n-1$ that $x^{(p^n-1)/\ell}\not\equiv1\pmod{g(x)}$. This will do it because we know that the order of $x$ in the multiplicative group $GF(p^n)^*$ is a factor of $p^n-1$, so if it is not a factor of any of maximal divisors $(p^n-1)/\ell$, then it must be the maximum.
Let us do the example from your comment: $p^n=3^4$, $g(x)=x^4+x^2+x+1$.
I assume that you have already checked that $g(x)$ is irreducible, for otherwise
$\mathbb{Z}_3[x]/\langle g(x)\rangle$ won't be the field $GF(81)$.
Here finding the factorization is easy, as $80=16\cdot5=2^4\cdot5$. We are to check that neither $x^{80/2}=x^{40}$ nor $x^{80/5}=x^{16}$ is congruent to $1$ modulo $g(x)$.
Let's do repeated squaring. We get a flying start as
$$
x^4\equiv x^4-g(x)=-x^2-x-1
$$
Therefore
$$
x^8=(x^4)^2\equiv(-x^2-x-1)^2=x^4+2x^3+2x+1\equiv 2x^3+2x^2+x\pmod{g(x)}
$$
and continuing
$$
x^{16}\equiv(-x^3-x^2+x)^2=x^6+2x^5+2x^4+x^3+x^2\equiv x^3+2\pmod{g(x)}.
$$
So we know that the order is not a factor of 16. Still need to check $40$.
We calculate
$$
x^{32}\equiv (x^3-1)^2=x^6+x^3+1\equiv x+2\pmod{g(x)},
$$
and finally
$$
x^{40}=x^{32}\cdot x^8\equiv(x-1)(-x^3-x^2+x)=-x^4-x^2-x\equiv1\pmod{g(x)}.
$$
Bummer, this means that the polynomial $g(x)$ is not primitive.
We can check similarly that $x^{20}\equiv-1\pmod{g(x)}$, so the order of $x$ is exactly $40$ (not a factor of either 20 or 8).
In general the problem of your second question is difficult (agree with Yoni and Marc), so you should expect a trick to do the specific case of $g(x)=x^4+x^2+x+1$, $a(x)=x+2$.
In the first part we saw that $g(x)$ is not primitive, so the (coset of $x$) only generates a subgroup $H$ of order 40 containing exactly half of the non-zero elements of $GF(3^4)$. We can seek to solve the discrete logarithmg problem in this subgroup. WARNING: As $x$ is not a primitive element, we may not succeed. It may happen that $a(x)\notin H$, and then no $j$ works.
Indeed, the following trick gets us started.
$$
x^2+x+1=x^2-2x+1=(x-1)^2=(x+2)^2.
$$
So if we have
$$
a(x)\equiv x^j\pmod{x^4+x^2+x+1},
$$
we also have
$$
x^{2j}=a(x)^2=x^2+x+1\equiv-x^4.
$$
Given that $x$ is of order $40$ we get that
$$x^{20}\equiv-1,$$
as $x^{20}$ is of order two, and $-1$ is the only element of multiplicative
order two.
Therefore
$$
x^{2j}\equiv x^{24}\pmod{g(x)}.
$$
As the discrete logarithm is defined modulo $\operatorname{ord}(x)=40$, we get
$$
2j\equiv 24\pmod{40}\Leftrightarrow j\equiv 12\pmod{20}.
$$
This leaves two choices $j=12$ and $j=32$.
While checking out primitivity of $g(x)$ we actually saw that $j=32$ works.
Didn't want to draw any attention to that earlier.
