Shortest Path using at most k colors
Here is a reduction from SAT to your problem. Let $\phi = C_1 \land \cdots \land C_m$ be a CNF on the variables $x_1,\ldots,x_n$. Consider the following graph with parallel edges (those can be easily eliminated if need be). There is a vertex for each variable and each clause, and additionally there are is a vertex $s$. There are $2n$ colors, one per literal, and we will choose $k := n$. The edges are:


From $s$ to $x_1$ there are two edges, colored $x_1$ and $\lnot x_1$.
From $x_{i-1}$ to $x_i$ there are two edges, colored $x_i$ and $\lnot x_i$.
From $x_n$ to $C_1$ there is an edge per literal in $C_1$, colored as the literal.
From $C_{j-1}$ to $C_j$ there is an edge per literal in $C_j$, colored as the literal.


Then $\phi$ is satisfiable iff there is a path from $s$ to $C_m$ which uses at most $n$ different colors.