Smallest NFA accepting concatenations of two words of the length $k$ which are different at all positions
Update: this doesn't answer the question that the original poster was looking for, and doesn't help with  the general case where $|\Sigma|&gt;2$, so the question remains open.



Here is a simpler construction, showing that in the case where $\Sigma=\{0,1\}$, $O(k \cdot 2^{2k})$ states suffice, and in fact you can recognize the language with a DFA with that many states.

Let's start by looking at the complement language:

$$\overline{L_k} = \{u \cdot v \in \Sigma^* : |u| = |v| = k, \exists i . u_i = v_i\}.$$

Notice that this can be recognized by a NFA with $2k^2 |\Sigma|$ states.  The NFA first guesses $i$ and a symbol $x$, then accepts all strings $u \cdot v$ where $u_i = v_i = x$.

Convert this to a DFA using the standard subset construction.  We get a DFA with $\le 2^{|\Sigma| k + 1} k$ states.  Now we can compute its complement, which is another DFA with the same number of states that recognizes $L_k$.  Since it is a DFA, it is in turn automatically a NFA, too.

This beats your construction for the case where $|\Sigma|=2$, but otherwise leads a NFA that's larger than your scheme.  However, I thought it might be of interest, both because it is so simple, and because it in fact provides a DFA (not just a NFA) to recognize your language $L_k$.