I have no idea how to even start proving the following theorem:
If $f_0, f_1: \mathbb{N}^r \rightarrow \mathbb{N}$ and $g_0, g_1: \mathbb{N}^{r+3} \rightarrow \mathbb{N}$ are primitive recursive, then also $h_0, h_1: \mathbb{N}^{r+1} \rightarrow \mathbb{N}$ that are for $i=0,1$ defined as
$h_i(0,x)=f_i(x)$ and $h_i(n+1,x)=g_i(n,h_0(n,x),h_1(n,x),x)$
Any hints/solutions will be much appreciated!
Define the function $p:(n,x)\mapsto \langle h_0(n,x),h_1(n,x)\rangle$ by recursion on $n$, using a primitive recursive pairing function. At $n=0$, use $\langle f_0(x),f_1(x)\rangle$, and at successors, combine your two recursions into one equation about this new function. One gets access to $h_0(n,x)$ and $h_1(n,x)$ by projecting the previous-value pair.
Update. The point is to define a single new function $p(n,x)=\langle h_0(n,x),h_1(n,x)\rangle$ by recursion, which will be a combination of the two functions, combined using any of the common pairing functions, such as $\langle r,s\rangle=2^r(2s+1)$. The new combined function is defined by recursion, since you know the "next" value of the pair $p(n+1,x)=\langle h_0(n+1,x),h_1(n+1,x)\rangle$ by consulting $n$, $x$ and the previous value of $p(n,x)=\langle h_0(n,x),h_1(n,x)\rangle$. So this new combined function $p$ is primitive recursive. It follows now by decoding the pairs that the functions $h_0$ and $h_1$ are primitive recursive separately.