Optimal path with multiple costs

This doesn't answer the NP-hardness, but you can solve the problem via integer linear programming as follows. For $(i,j)in E$, let binary decision variable $x_{i,j}$ represent the flow from $i$ to $j$. The problem is to minimize $z$ subject to: begin{align} sum_{(i,j)in E} x_{i,j} - sum_{(j,i)in E} x_{j,i} &= begin{cases} 1 &text{if $i=s$}\ -1 &text{if $i=t$}\ 1 &text{otherwise}end{cases} && text{for $iin V$}\ x_{i,j} &in {0,1} &&text{for $(i,j)in E$}\ z &ge sum_{(i,j)in E} c_{i,j}^r x_{i,j} &&text{for $rin{1,dots,k}$} end{align}

When $k geq 2$ we can reduce from the NP-hard partition problem. For a given multiset $S = {s_1, ldots, s_n}$ with even sum $X = sum_{i = 1}^n s_i$ create $n + 1$ vertices $s = v_0, ldots, v_n = t$, and for each $i = 0, ldots, n - 1$ connect vertices $v_i$ and $v_{i + 1}$ by two paths of costs, say, $(2, 2 + s_i)$ and $(2 + s_i, 2)$ (to avoid multiple edges). Then a partition of $S$ exists iff $P^* = 2n + X / 2$.