If you want to solve the complex roots using quadratic formula, try below :

$$x^3 + 512 = x^3+8^3 = (x+8)(x^2-8x+64) = 0$$

Solutions of any equation of the form $x^3=a^3$ are $a$, $a\omega$, $a\omega^2$, where $\omega$ is a cube root of unity, and $\omega \neq 1$. Usually one picks $\omega=e^{2i\pi/3}$

Hint: your full solution is $x=-8z$ where $z^3=1$. If you write $z=re^{i\theta}$ ($r\in\mathbb{R})$, then $z^3=r^3e^{i3\theta}=r^3(\cos(3\theta)+i\sin(3\theta))$. What can you say about $r$ and $\theta$ given that $z^3=1$?

I wanted to expand on what others have said as they don't explain what happens when you reach higher powers and I feel this solution is much easier.

For an equation in the form $$Z^n = x$$ You will have n solutions that will be evenly spaced around the origin.

So in this case we have: $$x^3 = -512$$ Which you correctly calculated one of the answers being: $$x = -8$$

Now that we know this first answer, we know the other 2 answers will be spaced 120 degrees (360/3 because there are 3 evenly placed answers) from this first answer.

So we can calculate these answers as follows: $$-8e^{\frac{120}{360}2\pi i} = 4-4\sqrt{3}i$$ and $$-8e^{\frac{240}{360}2\pi i} = 4+4\sqrt{3}i$$

Similarly if we have: $$x^4 = 4096$$ Our first answer can be calculated as $$x = \sqrt[4]{4096} = 8$$ And we know there will be 4 evenly spaced answers around the origin. Therefore we know they will be 90 degrees apart so the other 3 solutions will obviously be $$x = 8i,-8,-8i$$