So after some more help and an extensive reboot of my math skills, I found the answer. The information that I overlooked but is crucial to have is the **total length of the message**. Moreover, we also need a second message with slightly changed parameters. So we end up with:

 - $c_1$ = $(prefix_1 + secret + padding_1)^e mod \ n$
 - $c_2$ = $(prefix_2 + secret + padding_2)^e mod \ n$

Now, without the prefix change this would be a simple case of [Coppersmith's short pad attack](https://en.wikipedia.org/wiki/Coppersmith%27s_attack#Coppersmith%E2%80%99s_short-pad_attack). But the prefix requires some changes. This is where the length comes in handy: if we know the prefix change (e.g. a 0 byte becomes a 1 byte), and we know the total length, we can find the additional delta between the 2 ciphertexts (i.e. the delta besides from the padding), since we know which bits changed and can then add/substract $2^i$ for all changed $bit_i$

Example: if 

$prefix_1$ = 'hello\x00'

$prefix_2$ = 'hello\x01'

and the total message length (including secret and padding) is 100, we know that the 94th byte changed from 0 to 1. In bits, it means the 752nd bit changed from 0 to 1, hence adding $2^{752}$.

From here we can pick up the Coppersmith attack whereby the second polynomial needs to incorporate the difference:

$g_2(x,y) = (x+y+\Delta)^e - c_2$

The rest follows the classic attack. Now once we have $y$, we can use the [Franklin-Reiter related message attack](https://en.wikipedia.org/wiki/Coppersmith%27s_attack#Franklin-Reiter_related-message_attack) with the small exception that we need to also add the $\Delta$ we calculated from the prefix.

I realize this might have gone beyond the scope of my answer but I thought it was an interesting twist on existing exploits that could help someone out in the future :)