How to show that $A^3+B^3+C^3 - 3ABC = (A+B+C)(A+B\omega+C\omega^2)(A+B\omega^2+C\omega)$ indirectly?

We know $(A+B)\mid(A^n+B^n)$ for $n$ odd. What about with three terms? Compute

$$\mod A+B+C:\quad A^3+B^3+C^3\equiv-(B+C)^3+B^3+C^3\equiv-3BC(B+C)\equiv 3ABC.$$

So $(A+B+C)\mid(A^3+B^3+C^3-3ABC)=f(A,B,C)$. Further

$$f(A,B,C)=f(A,\omega B,\bar{\omega}C)=f(A,\bar{\omega}B,\omega C)=\rm etc.$$

by inspection so both $A+\omega B+\bar{\omega}C$ and $A+\bar{\omega}B+\omega C$ are also factors.

This argument exploits divisibility properties and inherent symmetry. It is generalized by the first proof (using matrix operations) mentioned in my other answer to compute $\Phi(G)$ for $G$ abelian.

HINT: If $A+Bw+Cw^2=0$ where $w$ is one of the three cube roots of unity

$\implies -A=Bw+Cw^2$

Cubing we get, $(-A)^3=(Bw+Cw^2)^3$

$\implies -A^3=B^3w^3+C^3w^6+3\cdot Bw\cdot Cw^2(Bw+Cw^2)=B^3+C^3+3BC(-A)$

$\implies A+Bw+Cw^2$ is a factor of $A^3+B^3+C^3-3ABC$

You can consider it as a polynomial in $A$ and attempt to factor it. So you want to find polynomials in $B$ and $C$, say $r,s,t$, such that

$$(A + r)(A+s)(A+t)=A^3-A(3BC)+B^3+C^3.$$

In particular, you need $r+s+t=0$, and you similarly have information about $rs+st+tr$ and $rst$. It's not hard to see that the roots are linear polynomials in $B$ and $C$, so they have the form $a+bB+cC$ for a constant $a$. You can plug this representation into the three equations you got from looking at the coefficients and solve.

If you need help getting started on the resulting equations, note that $rst$ has no constant term, so at least one of the roots has no constant term.