Complexity of the problem of words with fewest distinct letters accepted by a finite automaton
It is NP-hard for $k=3$.
The reduction is from 3-SAT-(2,2), which means that every clause contains $3$ literals and every literal occurs in at most $2$ clauses.

First of all, for simplicity, let's admit honestly that this problem has not much to do with automata.
Your problem is equivalent to the following:
Given an edge-colored digraph where each color occurs at most $k$ times, is there an $st$ path that uses at most $n$ colors?

For the reduction, the graph starts from $s$ with a path of length $n$, where $n$ is the number of variables of the 3-SAT-(2,2) input.
Each edge of this path is present twice, and all $2n$ edges have a different color.
The colors used when traversing this path correspond to which variables are true.
After this path, there is another path whose length is the number of clauses.
Here every edge is thrice, where the colors correspond to the literals of the clause.
We can get to the end of this path using no extra colors (thus in total $n$) if and only if the 3-SAT-(2,2) input is satisfiable.