Graph with minimum number of edges having given sets of nodes as its paths
This problem is NP-complete, even for the special case $|P_k|\le 3$. I will give a reduction from Vertex Cover. I will refer to the sets $P_1,\ldots,P_k$ in the question as constraints: binary or ternary, depending on their cardinality.

Let $(V',E',k)$ be an instance of Vertex Cover: Is there a subset $S$ of $k$ vertices from $V'$ such that $S$ covers (that is, intersects) all edges in $E'$?

We add a distinguished vertex $\bullet$; that is, $V=V'\cup\{\bullet\}$. We add binary constraints for all pairs of vertices in $V'$: for each $\{i,j\}\subseteq V'$, we add the constraint $\{i,j\}$. We then add ternary constraints for each edge in $E'$: for each $\{i,j\}\in E'$, we add the constraint $\{i,j,\bullet\}$.

We ask whether there is a graph with $\binom{|V'|}{2}+k$ edges that satisfies the above constraints. The answer (yes or no) is an answer to the Vertex Cover question.

Why would that work? Because of the binary constraints, we know that edge $\{i,j\}$ is selected. So, the only task that remains is to pick between $\{i,\bullet\}$ and $\{j,\bullet\}$. That's exactly the task we have in the original Vertex Cover problem: Pick which endpoint of an edge we use to cover it.