When is Viterbi's algorithm practical?
There is no threshold of $k$. Viterbi's algorithm has a certain complexity. For small enough $k$, you will be able to run Viterbi's algorithm on the given hardware at the given speed. For larger values of $k$, Viterbi's algorithm would be too slow. The exact threshold depends on your hardware (its capabilities, and how much "space" is available to implement the algorithm), and on the required speed. Viterbi's algorithm is optimal, and so it should probably be preferred over other algorithms when the constraints allow using it.