  In arithmetic and algebraic geometry, superspecial (s.sp.\ for short) curves
are one of the most important objects to be studied, with applications to
cryptography and coding theory. If $g \geq 4$, it is not even known whether
there exists such a curve of genus $g$ in general characteristic $p > 0$, and
in the case of $g=4$, several computational approaches to search for those
curves have been proposed. In the genus-$4$ hyperelliptic case, Kudo-Harashita
proposed a generic algorithm to enumerate all s.sp.\ curves, and recently
Ohashi-Kudo-Harashita presented an algorithm specific to the case where
automorphism group contains the Klein 4-group. In this paper, we propose an
algorithm with complexity $\tilde{O}(p^4)$ in theory but $\tilde{O}(p^3)$ in
practice to enumerate s.sp.\ hyperelliptic curves of genus 4 with automorphism
group containing the cyclic group of order $6$. By executing the algorithm over
Magma, we enumerate those curves for $p$ up to $1000$. We also succeeded in
finding a s.sp.\ hyperelliptic curve of genus $4$ in every $p$ with $p \equiv 2
\pmod{3}$. As a theoretical result, we classify hyperelliptic curves of genus
$4$ in terms of automorphism groups in the appendix.
