Constructive proof of decidability of finite Halting-problem-style set that does not use table lookup
There is no general way to find a decider TM for $L_k$

You are correct that $L_k$ is recursive because, being a subset of the
finite set $\Sigma^k$, it is also finite.

You would like to rather find a decider TM for $L_k$, and you suggest
some techniques. Without even going into the details of these
techniques and why they do not work, you do not stand any chance of
ever succeeding.

The first thing you should notice is that the finiteness argument
tells you that there exists a decider TM $M_k$ for the language $L_k$,
but it does not tell you what this TM is. It is an example of a
non-constructive proof: you prove that a decider exists, but you
cannot tell which it is.

Now, suppose that, given $k$, you have a procedure $\mathcal P(k)$ to
find such a decider $M_k$ for the language $L_k$ (rather than just
prove it exist). Then, given any Turing machine $M$, then there is an
integer $k'$ such that $|\langle M\rangle|=k'$, so that $\langle
M\rangle\in \Sigma^{k'}$. Then you can use the procedure $\mathcal P$
to find a decider TM $M_{k'}$ that can determine whether $\langle
M\rangle\in L_{k'}$. So you have a way to decide whether the TM $M$
halts on empty input. And this works for any TM $M$. However, this is
not possible, because it is undecidable whether a given TM $M$ halts
on empty input.

So the procedure $\mathcal P$ cannot exist.

Since you are looking for a general way to find the decider TM
$M_{k'}$, you cannot succeed because that method would be precisely a
procedure such as $\mathcal P$.

Note that this proof could still leave the (very remote) possibility
of finding a decider for some specific values of $k$, but you would
have to identify precisely the concerned values, and the method would
not work for all values of $k$. I am not advising you to try.