If k=1 then n is at most 2 if you expect the graph to be connected. If k=2 then you have a cycle or path with diameter about n or n/2. ( I don't know if diameter is by counting edges or vertices, but the rest of this post will talk in approximate terms, so I won't care for exact results in what follows.) So consider k being 3 or greater.

Since you need n-1 edges, let's see what you can do with them. Try constructing a k-ary tree (root has k branches, some others have k-1 or fewer, most have degree 1), which leads to a diameter about c=log_k (n^2), which is small compared to n. So you need to add more edges only when d is smaller than c, or about log n or smaller.

Suppose you decide to add an edge to two leaves on the tree. Usually you won't reduce the graph diameter this way, but if you choose the leaves that have a common ancestor more than d/2 away, you have a start. For this edge affects not only those two leaves, but all leaves which are distance d/2 away from one of the two vertices. This is about k^d pairs of vertices brought to within the proper diameter by just one edge. Since there are about k^c pairs to deal with, you will need at least about k^(c-d) edges to follow this construction. For very small d, this may result in a number of edges which is a fractional power of n. (If d is too small, it may not be possible without violating the Max degree constraint. In which case, I'd really like to see the graph that does satisfy both constraints.)

Gerhard "More Than Just A Star-t" Paseman, 2018.09.14.