I have a full proof in type $A$, and most of a proof in the other types. Notation: $\alpha_1$, $\alpha_2$, ..., $\alpha_n$ are the (positive) simple roots, $\Phi^{+}$ is the set of all positive roots, $\rho$ is determined by the condition $\langle \alpha^{\vee}_i, \rho \rangle =1$ for all $i$. The element $\sigma$ is defined as $\sum_i \alpha_i$

I'll write $\alpha \geq \beta$ to indicate that $\alpha -\beta = \sum c_i \alpha_i$ for $c_i \in \mathbb{Z}_{\geq 0}$. So the condition that $\lambda-\mu$ is in the interior of the positive cone and occurs in $V_{\lambda}$ states that $\mu \leq \lambda - \sigma$. Our strategy is to show that $$K_{\lambda \mu} \geq K_{\lambda (\lambda - \sigma)} = \# (\mbox{number Coxeter elements}).$$

The gap in this argument is to give a proof in all types of

The Annoying Lemma: Suppose that $\beta \geq \delta$ and both $\beta$ and $\delta$ are dominant. Then there is a sequence of dominant weights $\gamma_0$, $\gamma_1$, ..., $\gamma_N$ such that $\beta = \gamma_0$, $\gamma_N=\delta$ and $\gamma_i - \gamma_{i+1} \in \Phi^{+}$.

Note that the Annoying Lemma is false if we ask for $\gamma_i - \gamma_{i+1}$ to be a simple root. For example, write dominant $GL_3$ weights as partitions in the usual way and take $\beta = (3,2,1)$ and $\delta = (2,2,2)$. Then the Lemma is true, because $\beta - \delta = (1,0,-1)= \alpha_1 + \alpha_2$ is a positive root. However, either of the two sequences $(\beta, \beta-\alpha_1, \delta)$ or $(\beta, \beta-\alpha_2, \delta)$ has a non-dominant element in the middle (namely, $(2,3,1)$ and $(3,1,2)$ respectively.)

Proof of $K_{\lambda \mu} \geq K_{\lambda (\lambda - \sigma)}$ assuming the Annoying Lemma: We immediately reduce to the case that the Dynkin diagram is connected. Also, the $SL_2$ case is immediate, so we assume we are not in it. With those reductions made, $\rho-\sigma$ is dominant. Since $\lambda$ is regular dominant, we have that $\lambda - \rho$ is domininant, so $\lambda - \sigma$ is dominant. We may therefore apply the Annoying Lemma to obtain a chain $\gamma_0 = \lambda - \sigma$, $\gamma_1$, $\gamma_2$, ..., $\gamma_N = \mu$ where $\gamma_i - \gamma_{i+1} \in \Phi^+$.

It is enough to show that $K_{\lambda \gamma_{i+1}} \geq K_{\lambda \gamma_{i}}$. Restrict to the $SL_2$ corresponding to $\pm (\gamma_i - \gamma_{i+1})$. Then the weights $\gamma_i$ and $\gamma_{i+1}$ lie on the same $SL_2$ string, and the condition that they are both dominant says that $\gamma_{i+1}$ lies nearer the center than $\gamma_i$, so $K_{\lambda \gamma_{i+1}} \geq K_{\lambda \gamma_{i}}$ as desired. $\square$

Proof that $K_{\lambda (\lambda - \sigma)} = \#(\mbox{number of Coxeter elements})$.

We recall the BGG resolution $$0 \leftarrow V_{\lambda} \leftarrow M_{\lambda} \leftarrow \bigoplus_{i} M_{\lambda - (\langle \alpha_i^{\vee}, \lambda \rangle +1) \alpha_i} \leftarrow \cdots$$ where $M_{\kappa}$ is the Verma module with highest weight $\kappa$. Since $\lambda$ is regular dominant, $\langle \alpha_i^{\vee}, \lambda \rangle \geq 1$ and thus $\lambda - \sigma = \lambda - \sum_j \alpha_j$ is not a weight of $M_{\lambda - (\langle \alpha_i^{\vee}, \lambda \rangle +1) \alpha_i}$. So the multiplicity of $\lambda - \sigma$ in $V_{\lambda}$ is the same as in $M_{\lambda}$; that is to say, it is the multiplicity of $\sigma$ as a weight of the universal enveloping algebra of $\mathfrak{n}_+$.

Let $e_1$, $e_2$, ..., $e_n$ be the Chevalley generators of $\mathfrak{n}_+$. Then $U(\mathfrak{n}_+)$ is generated by the $e_i$ modulo the Chevalley-Serre relations. We see that a monomial in the $e_i$ is of degree $\sigma$ if and only if it uses each $e_i$ once, and the only Serre relations in such low degree are those of the form $e_i e_j = e_j e_i$ when $A_{ij} =0$. So the multiplicity of $\sigma$ as a weight of $U(\mathfrak{n}_+)$ is the number of permutations of $e_1$, ..., $e_n$, up to interchanging commuting elements; this is precisely the description of the Coxeter elements. (It is also not hard to directly prove, using for example PBW bases, that the number is $2^{n-1}$, but I thought this was more fun.)

I have a proof of the Annoying Lemma in type A, but this is getting quite long, so I think I'll upload this and think a bit more about the general case first.