Minimum sub-tree of a graph that covers each color at least once
The OP has noticed that "for k=3, it becomes tricky". Indeed, the problem with variable $k$ with respect to $|V|$ is NP-complete and, hence, NP-hard.

Let us formalize the problem so as to able to prove it rigorously. This colored nodes covering problem, called for brevity CNC, is defined in decisional form as follows:

Instance:


a connected graph $G = (V, E)$;
a positive integer $k\le|V|$ and a map $C:V\to\{1, 2, \cdots, k\} $, called coloring map with $|C(V)|=k$; 
a positive integer $m$


Question: Is there a subtree $T=(V', E')$ of $G$ that $|E'|\le m$ and $|C(V')|= k$?

Claim: Colored nodes covering problem (CNC) is NP-complete with respect to $|V|$.



Proof of the Claim.

It is easy to see that CNC is in NP. Let us reduce the Steiner tree problem, called for brevity ST, one of the NP-complete problems in Karp's original paper to CNC. 

Let us recall ST can be defined in decisional form as follows:

Instance:


a connected graph $G = (V, E)$;
a subset of the nodes $R\subseteq V$ , called terminal nodes; 
a positive integer $m$.


Question: is there a subtree of $G$ that includes all the nodes of $R$ and that contains at most $m$ edges?

Let us show a polynomial-time reduction from ST to CNC by building an instance of CNC starting from a generic instance of ST. Given a generic instance $s$ of ST, defined by a graph $g=(V,E)$, the set of terminals $R=\{v_1, v_2, \cdots, v_k\}\subseteq V$, and the
upper-bound $m$, define an instance $c$ of CNC as the following.


the same graph $G=(V,E)$.   
the coloring $C: V\to\{1,\,2,\,\cdots,k,\,k+1\}$, $C(v_i)=i$ for $1\le i\le k$ and $C(v)=k+1$ otherwise.
the same upper bound $m$.


If the induced graph $G[R]$ is connected, then both $s$ and $c$ can be determined in polynomial time in $|V|$ (in fact, constant time), since the spanning tree of $G[R]$ is a tree with the minimal number, $k-1$ of edges that can include all vertices of $R$.

Otherwise let us assume $G[R]$ is not connected. Then any subtree of $G$ that contains all nodes of $R$ must contain at least one node that is not in $R$, which must be colored $k+1$. For any subtree $H$ of $G$, $H$ includes all the nodes of $R$ and contains at most $m$ edges if and only if $H$ includes nodes of every possible color under $C$ and contains at most $m$ edges. That is, $s$ has a yes answer if and only if $c$ has a yes answer.

It is easy to see that the transformation from $s$ to $c$ can be done in polynomial time (in fact, constant time). So we have reduced ST to CNC by a polynomial-time reduction.



Bonus exercise: is the colored nodes covering problem with fixed $k$ NP-hard? This is not an easy exercise. Here is a hint.


   No. My first step toward demonstrating the existence of a polynomial algorithm is noticing that there will be at most $|V|^k$ choices of the nodes in the subtree that will be mapped to all colors. ($|V|^k$  can be lowered to $(|V|/k + 1)^k$, which does not affect the logic though). It will take some time to reach a full proof.