$k$ is indeed a constant. Usually we only require asymptotic complexity computations (i.e. "big O notation", like $O(|V|+|E|)$).
Sometimes, as in this case, we would like you to consider the effect of the constant.
In your answer, you can either write the complexity as $O(|V|+|E|)$ or, say, $O(k^3|V|+|E|)$, if the dependence on $k$ is cubic. Either will is fine, and will get you full points.
The algorithm for b) must be independent of $k$, so changing the value of $k$ won't change the running time AT ALL.
The algorithm for a) might be dependent on $k$ or independent of $k$ - whatever you like. (Notice we are fine with exponential dependence on $k$, as $k$ is a constant… )
Let me say, though, that we recommend you don't try to find an algorithm whose complexity doesn't depend on $k$ for a)… If you do, make sure your proof is correct (I have not yet personally seen any such algorithm with a correct proof).
