For each permutation I only considered initial candy distributions where cat #M shares (thus for each permutation there are only (M-1)! possible distributions). Also I used bitwise operations and multi-threading but it still took 12 hours. I have some ideas on how to prune the search space further. For example it seems that cats #M and #M-1 can always be swapped, though I have no idea why this is the case. Also permutations like 354789612 can be discarded because if cat #3 receives a candy then cat #5 also gets one which implies that cat #5 will eventually have 6 candies.

Just finished a computer search, there are no 11-PPMs

There are definitely 10-PPMs. In fact, here's an exhaustive list of all PPMs with M<11.

@a3nm Yes, it seems that for $k=2$ the sparse rulers are the optimal embedding. But anyways, the bound can be derived from the fact that for a fixed $k$, ${n \choose k}$ is a polynomial of degree $k$. Thus $\frac{{n \choose k}}{n}$ is approximately a polynomial of degree $k-1$. Now we want to find some function $f(n)$ so that ${f(n) \choose k}$ grows like a polynomial of degree $k-1$. This means that $f(n)$ has to grow like a polynomial of degree ${1-\frac{1}{k}}$ since if you multiply that by $k$ you get the desired growth rate of $k-1$