OK, this is an attempt to amplify the very brief sketch of what could be done with the regularity lemma. Of course, I'll still give a sketch, but I'll try to say more clearly what I mean.
First of all, the regularity lemma itself says that for every $\epsilon>0$ there exists a constant $K$ such that for every graph $G$ you can partition the vertex set into $k\leq K$ sets $V_1,\dots,V_k$ of roughly equal size such that for all but $\epsilon k^2$ of the pairs $(i,j)$ the induced bipartite subgraph (or just subgraph if $i=j$) is $\epsilon$-regular. Here, $\epsilon$-regular means something like "behaves to within $\epsilon$ like a typical random graph of the same density". I won't say precisely what that means, but I hope it will be plausible that this quasirandomness property will have the consequences I claim it has.
Now if we $r$-colour a complete graph, that's the same as partitioning the edges into $r$ graphs. It turns out that a simple modification of the proof of the regularity lemma allows us to apply it to all these $r$ graphs at once, obtaining a single partition that works for all of them. (Of course, now the constant $K$ will depend on $r$ as well as on $\epsilon$.) What I mean here is that for all but $\epsilon k^2$ pairs, all $r$ of the induced bipartite subgraphs are $\epsilon$-quasirandom.
For many purposes, all random graphs of a given density behave in the same way. That is the case here, so once we have our partition the only information we really care about is the densities of the various colours in the various bipartite graphs. That is, we care about numbers like $\alpha_{ijs}$ where that is the density of edges in $V_i\times V_j$ that are coloured with colour $s$.
Let's call a pair $(i,j)$ good if all the colour classes of edges in $V_i\times V_j$ are quasirandom. The main consequence we need of quasirandomness is that if you have $d$ of the sets $V_1,\dots,V_k$ such that all the pairs from among those $d$ sets are good, then the number of cliques of colour $s$ will be approximately $|V_{i_1}|\dots|V_{i_d}|\prod_{j,h\leq d}\alpha_{i_ji_hs}$, where $V_{i_1}\dots V_{i_d}$ are the sets in question. Since almost all pairs are good, almost all $d$-tuples generate $\binom d2$ pairs that are all good. It follows that up to some error that tends to zero with $\epsilon$, the number of monochromatic cliques, as a fraction of $n^k$, depends just on the numbers $\alpha_{ijs}$. (To see this, you just add up over all possible $d$-tuples.) It follows that the minimum number of monochromatic cliques can be found by calculating a minimum over all choices of $\alpha_{ijs}$. Since $k$ is bounded above by a number that depends on $\epsilon$ and $r$ only, this is in principle a finite problem for any given $\epsilon$, $d$ and $r$. (However, the bound on $k$ is absolutely vast, so this problem is absolutely not feasible in practice.) More to the point, it proves that $A(n,d,r)/n^d$ tends to a limit as $n$ tends to infinity with fixed $d$ and $r$. (Apologies -- I've changed your $k$ to a $d$ and your $d$ to an $r$. That's because I chose $k$ in the regularity lemma, which I now regret.)
It remains to establish that this limit isn't zero. A quick and dirty way of doing that is to make $\epsilon$ so small that there must exist $R(r,d)$ of the sets $V_i$ such that all pairs are good, where $R(d,r)$ is the number needed to get a monochromatic clique of size $d$ when you have $r$ colours. For each pair we can now choose the colour that occurs most frequently and colour that pair with that colour. Applying Ramsey's theorem, we obtain a monochromatic clique of size $d$, which translates into $d$ sets $V_{i_1}\dots V_{i_d}$ that are all quasirandomly joined in that colour with density at least $1/r$. By quasirandomness, that gives us (to within a small error) at least $r^{-\binom d2}|V_{i_1}|\dots|V_{i_d}|$. Each $V_i$ has at least $n/K$ elements, and $K$ is independent of $n$, which completes the proof.
