Added yet later: I think I may be able to use similar ideas to prove a lower bound. Take $2^k$ pairs $x_sy_s$, where each s is a vertex of the discrete k-dimensional cube. For each i between 1 and k form a clique by joining every $x_s$ such that $s_i=0$ to every $y_s$ such that $s_i=1$, and also the other way round. Then for every s not equal to t we cover both the edges $x_sy_t$ and $x_ty_s$. Also, we never cover the edge $x_sy_s$, and the number of cliques is 2k. One more thing ... each vertex is contained in precisely 2k cliques so far. We now add in all the cliques of size 2 with vertex sets $x_s,y_s$. So now each vertex is in precisely 2k+1 cliques. So we have a minimal system of at least $2^k$ cliques, with each vertex in 2k+1 of them. Thus, the bound for the original problem (if my reasoning is correct) is at least exponential.

This isn't an answer but simply a way of thinking about the question that I quite like.

In the reverse direction, if we have a bunch of cliques that cover the complete graph, we can associate with each vertex the set of cliques that contain that vertex, and the condition that the sets intersect is precisely the condition that the cliques cover all the edges of the graph. So it's a trivial reformulation, but I find it a helpful alternative picture of what is going on.

This isn't an answer but simply a way of thinking about the question that I quite like. (Later: see below for an attempted proof.)

In the reverse direction, if we have a bunch of cliques that cover the complete graph, we can associate with each vertex the set of cliques that contain that vertex, and the condition that the sets intersect is precisely the condition that the cliques cover all the edges of the graph. So it's a trivial reformulation, but I find it a helpful alternative picture of what is going on.

Added later: here is an attempt to improve the bound to $k^{Ck}$. I think it works but have not 100% checked.

Take a minimal subcollection S of the cliques that covers the complete graph, and suppose that S contains $N$ cliques.

Because S is minimal, for each clique in S there is some edge contained in just that clique and no other clique from S. Since each vertex is in at most k cliques, no vertex is contained in more than k of these edges. So we can find a collection of at least N/k disjoint edges, each of which is contained in just one clique from S. Let M be the number of edges in this set.

At this point I'm going to be very sketchy. I want to prove that M is at most $k^{Ck}$ by showing that if it's bigger than that, then I'm going to have to have a vertex that's contained in more than k cliques.

Let the M disjoint edges be called $x_1y_1,...,x_My_M$, and let $K_i$ be the clique that contains $x_i$ and $y_i$. Let's from two cliques $L_i$ and $M_i$ from $K_i$, one obtained by removing $x_i$ and one by removing $y_i$. Then between them $L_i$ and $M_i$ cover all the edges that $K_i$ covers, apart from the edge $x_iy_i$. So we'll be done if we can show that some vertex has to be contained in more than 2k of the cliques $L_i$ and $M_i$, together with other cliques that don't contain any of the edges $x_iy_i$.

So our assumption now is that we have a bunch of cliques, and for each i no clique contains both $x_i$ and $y_i$, and yet all other pairs $x_iy_j$ or $y_ix_j$ are joined in at least one of the cliques. We want to show that some vertex is contained in at least 2k cliques.

In particular for each i and j (not equal) we must have a clique that joins $x_i$ to $y_j$ or $y_i$ to $x_j$ (since in fact we must do both). But no clique ever contains both $x_i$ and $y_i$ or both $x_j$ and $y_j$.

Given any clique $K$ from the new collection, the set of pairs ij such that $K$ joins $x_i$ to $y_j$ or $y_i$ to $x_j$ is a bipartite graph. (Its vertex sets are the set of i such that $K$ contains $x_i$ and the set of i such that $K$ contains $y_i$.) So we would like to cover a complete graph with M vertices with bipartite graphs, in such a way that no vertex is contained in more than 2k of those bipartite graphs.

An averaging argument (this is the sketchy bit) should show that we can discount bipartite graphs with a vertex set that is smaller than cM/k, since they do not contribute enough to the average degree. But if we just use bipartite graphs with vertex sets of size at least cM/k, then we can use the following standard argument. Let $X_1$ be one of the vertex sets of the first bipartite graph. Then none of the edges inside $X_1$ are covered. So by induction we know that the number of vertices in $X_1$ is at most M(k-1) (where the M that we are trying to bound is M(k)). But it's also at least cM(k)/k, so we get a bound of $(k/c)^k$ for M.