How to generate a Markov Matrix efficiently

Here's something even more compact than my proposal in the comments:

Standardize[RandomReal[1, {4, 4}], 0 &, Total]

If you must have a left stochastic matrix where all the entries should be greater than a set value, you can do rejection sampling: keep generating a matrix as long as the smallest value is smaller than the cutoff:

While[Min[sm = Standardize[RandomReal[1, {4, 4}], 0 &, Total]] < 0.1]; sm

---

If a doubly stochastic matrix is desired (that is, all columns and all rows sum to unity), some more trickery is necessary:

While[Min[dsm = FixedPoint[Standardize[Transpose[Standardize[#, 0 &, Total]],
                                       0 &, Total] &, RandomReal[1, {4, 4}],
                           SameTest -> (Norm[#1 - Transpose[#2], "Frobenius"] <
                                        1.*^-12 &)]] < 0.1]; dsm

I make no guarantees on the distribution followed by the matrices generated by either method.

Assuming you want uniformly distributed n-dimensional probability vectors with a minimum value, I think you can use:

MarkovMatrix[n_, min_:0] := If[min n<1,
    Transpose @ RandomPoint[Simplex[IdentityMatrix[n](1-min n)], n] + min,
    $Failed
]

For example:

MarkovMatrix[4, .1] // TeXForm

$\left( \begin{array}{cccc} 0.378616 & 0.267013 & 0.416824 & 0.142604 \\ 0.14229 & 0.305494 & 0.177654 & 0.203273 \\ 0.231628 & 0.175853 & 0.154734 & 0.178135 \\ 0.247466 & 0.251641 & 0.250788 & 0.475988 \\ \end{array} \right)$

Here is my idea

make[n_] := ConstantArray[0.1, {n, n}] + (
                 (1 - 0.1 n) #/Total[#, {2}] &[RandomReal[{0, 1}, {n, n}]])

Because of the minimum you specified for each entry, this works for $n<11$ only. Did you consider letting the minimum value dependent on $n$ in a decreasing manner?