You can limit the question to real symmetric matrices $A$ (with diagonal $0$ if desired). For large enough $k,$ the matrix $A+kI$ will be positive definite and you are then allowed to change all the diagonal entries.

For $n=2m-1$ and $n=2m$ you can't always get $k \lt m.$ The upper right $m \times m$ submatrix can be chosen to have rank $m.$ For example it could be lower triangular with $1$'s on the diagonal. 

We can get it this low for $n=1,2,3$ and can We can leverage that to show (see below) that the rank can be, for some matrices, be reduced to about $\frac{2n}{3}$ but no lower.


In a few small attempts for $n=3,4,5$ I always managed to get the rank down to $m.$ However I might not have looked hard enough.

Here is one example:

$$\left[ \begin {array}{ccccc} a&t&1&0&0\\ t&b&0&1&0\\ 1&0&c&0&1\\ 0&
1&0&b&t\\ 0&0&1&t&a\end {array} \right]$$

where $t$ is a yet to be specified constant and $a,b,c$ are values we are free to set on the diagonal. We actual are allowed $5$ choices on the diagonal but I attempted this pattern since the rest of the matrix has it.

Note first that, just from the three $0$'s and three $1$'s at the lower left, it is clear that the last three rows are independent so the rank will never be less than $3.$

Doing some row operations it turns out that rank three can be obtained by setting $b=\frac{t^2+a}a$ and $c=\frac{t^2+2a}{a^2}$ where $a$ is any non-zero value. With $a=1,$

$$\left[ \begin {array}{ccccc} 1&t&1&0&0\\ t&t^2+1&0&1&0\\ 1&0&t^2+2&0&1\\ 0&
1&0&t^2+1&t\\ 0&0&1&t&1\end {array} \right]$$

which does, indeed, have rank $3.$


**LATER**

By changing the diagonal entries we get the rank of $$M_2=\left[ \begin {array}{cc} 0&1\\ 1&0\end {array} \right]$$ down from $2$ to $1$ but no lower.

The rank of $$M_3=\left[ \begin {array}{ccc} 0&1&0\\ 1&0&1\\ 0&1&0\end {array} \right]$$ is $2$ and no change of the diagonal entries can get it lower.

Putting blocks of $M_3$ down the diagonal along with a single block of $M_2$ or $M_1=[0]$ we get a matrix such that we can reduce the rank to be $2q,$ but no smaller, for $n=3q$ and $n=3q+1,$ and a matrix such that we can reduce the rank to be to be $2q+1$ for $n=3q+2.$ 

It might be that there are other matrices which cannot be reduced this far.