The OP is correct in pointing out that "Local Non Satiation (LNS) only says there's a (utility) increasing direction but doesn't say which direction it is increasing". Namely, we entertain the possibility on dealing with "bads" also, not only with "goods". MWG Microeconomic Theory book page 43 Figure 3.B.1 depicts exactly such a situation.
But it is the case that, when the bundle set is $\mathbb R_+$, under LNS not all items can be bads. Because then, the zero vector will be a point of satiation (and so it would violate the LNS assumption).
So using non-negative quantities of items and imposing LNS forces us to consider only the cases where at least one item in the bundle is a good and not a bad, in which case "more is better" for this item.
Then, we can prove that local non-satiation implies exhaustion of the available budget.
Ad absurdum, assume that $px^* < m$. Under LNS for every $\epsilon >0$, there exists a $y(\epsilon)$ that is more preferred to $x^*$. If some $y(\epsilon)$ is feasible, $py(\epsilon) \leq m$, then $x^*$ cannot be the optimal choice in the first place.
So the question is : Is it possible that all $y(\epsilon)$ that are preferred to $x^*$ under LNS, are infeasible, $py(\epsilon)>m,\;\; \forall \epsilon>0$?
I guess the OP can take it from here.