L = { , M is a DFA accepting all strings except finitely many
It is indeed decidable, but your solution is not quite correct.

To restate the problem, we're given an encoding $\langle M\rangle$ of a DFA $M$, and we want to decide whether accepts every possible string except a very small (finite) number of them. So for each DFA encoding in this language $L$, there's an associated $x_{M} \in \mathbb{N}$ (which we don't know) and $M$ only rejects $x_{M}$ strings.

So for example, a DFA $A$ that accepts everything (i.e. $\Sigma^{\ast}$) would be in $L$, because $x_{A} = 0$, which is definitely a finite number. Similarly if we have a DFA $B$ which rejects the string $a$, but accepts everything else, this would be in $L$ as $x_{B} = 1$, which is also finite.

Right, now to showing that this decidable for every DFA $M$. To do this we need to make a key observation, similar to what you were proposing, but sort of reversed; if a DFA rejects only finitely many strings, they must all have length smaller than $k-1$, where $k$ is the number of states. Why is this true? Suppose that it rejects a string with length greater than $k-1$, then to process this string the DFA must go around a cycle (either a loop or a longer path, or some combination thereof), but if it can go around the cycle once, it can do it twice, or three times, or any number of times. So if there's at least one long rejected string, there must be an infinite number of rejected strings.

Using this, we can see that if it rejects a string of length somewhere between $k$ and $2k$ (a single go around the cycle can use each state at most twice), then it must reject an infinite number of strings.

Finally we can get to our decider:


On input $\langle M \rangle$ where $M$ is a DFA:


One by one, enumerate all strings of length $k$ to $2k$.


Simulate $M$ on each string.
If $M$ rejects any tested string, reject.

If $M$ rejects no strings of length between $k$ and $2k$, accept.