This is the answer to a slightly modified version of
the problem. I hope that it would also lead to a solution
of the original version.

As I point out in my answer to Math StackExchange question 66430
("What is the distribution of gaps?"),
if, in addition to the gaps $G_1=a_1$and $G_j:=a_j-a_{j-1}$ for $2\leq j\leq n$,
you introduce final gap $G_{n+1}=(m+1)-a_n$,
the random vector $(G_1,G_2,\dots, G_{n+1})$ gives a random composition
of the number $m+1$. That is, all outcomes $(g_1,g_2,\dots, g_{n+1})$
with $$g_1+g_2+\cdots+g_{n+1}=m+1,\quad g_j\geq 1$$
are equally likely. There are $m\choose n$ such compositions, as
found using stars and bars.

Then $Pr(a_{\max}\leq k)$ (where *my* maximum includes the final gap)
is just the proportion of compositions using numbers from $1$ to $k$.
By inclusion-exclusion and stars and bars, this probability is
$$Pr(a_{\max}\leq k)={\sum_{x} (-1)^x {m-xk\choose n}{n+1\choose x}\over{m\choose n}}.$$