It is easier to describe non-good (*bad*) numbers with respect to a given prime $p$. For each such number $k$, there exists a prime $q$ such that $q\mid k$ and $q\mid (p^k - 1)$. It follows that $k$ is multiple of $m_p(q):=q\cdot \mathrm{ord}_q(p)$, where $\mathrm{ord}_q(p)$ is the multiplicative order of $p$ modulo $q$ (which is a divisor of $q-1$). Hence, the set of bad $k$ is formed by the union
$$\bigcup_{q\in\mathbb{P}\atop q\ne p} m_p(q)\mathbb{Z}.$$ 

**UPDATE.** It also follows that $k$'s bad for all primes $p$ form the set
$$\bigcup_{q\in\mathbb{P}\atop q\geq 3} q(q-1)\mathbb{Z}.$$ 
Correspondingly, the density of $k$'s that are good for all primes equal
$$\prod_{q\in\mathbb{P}\atop q\geq 3} \left(1-\frac1{q(q-1)}\right)\approx 0.7479.$$