Using resultants can greatly help. For example, knowing that $\sqrt[5]{2}$ is a zero of $P(x)=x^5-2$ and $1-\exp\frac{2\pi i}{5}$ is a zero of $Q(x)=(x-1)^5+1$, we conclude $\sqrt[5]{2}\cdot (1-\exp\frac{2\pi i}{5})$ is a zero of $\mathrm{Res}_y(P(y),y^5Q(\frac{x}{y})$. In PARI/GP:
? polresultant(y^5-2,y^5*((x/y-1)^5+1),y)
%1 = x^25 + 2500*x^15 + 50000*x^5
? factor(%)
%2 =
[ x 5]
[x^20 + 2500*x^10 + 50000 1]
That is, we conclude that the minimal polynomial is $x^{20} + 2500x^{10} + 50000$. Numerical verification:
? subst(x^20 + 2500*x^10 + 50000, x, 2^(1/5)*(1-exp(2*Pi*I/5)) )
%3 = 5.380530270144733809 E-34 - 2.104034275277802617 E-34*I
(the default precision is 38 decimal digits)