The answer is $30$.
Firstly, since $a^4 + a + 1 = 0$, we have
$$a^5 + 2a + 1 = a(a^4 + a + 1) - a^2 + a + 1 = -a^2 + a + 1.$$
Let $y = -x^2 + x + 1$. Then $x = \frac{1 \pm \sqrt{-4y+5}}{2}$. Now,
$$\begin{aligned} 0 &= x^4 + x + 1 \\ &= \left( \frac{3 - 2y \pm \sqrt{-4y+5}}{2} \right)^2 + \frac{1 \pm \sqrt{-4y+5}}{2} + 1 \\ &= \frac{2y^2 - 8y + 7 \pm (3 - 2y)\sqrt{-4y+5}}{2} + \frac{1 \pm \sqrt{-4y+5}}{2} + 1 \\ &= y^2 - 4y + 5 \pm (2 - y)\sqrt{-4y+5}. \end{aligned}$$
This implies $(y^2 - 4y + 5)^2 = (y - 2)^2(-4y + 5)$, which is a degree $4$ polynomial equation. Therefore, $a^5 + 2a + 1$, $b^5 + 2b + 1$, $c^5 + 2c + 1$ and $d^5 + 2d + 1$ are roots of the equation
$$f(y) = (y^2 - 4y + 5)^2 - (y - 2)^2(-4y + 5) = 0.$$
Note that $f$ is monic. So it is exactly $x^4 + px^3 + qx^2 + rx + s$. Thus,
$$p + 2q + 4r + 8s = 8f\left(\frac{1}{2}\right) - \frac{1}{2} = 30.$$