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.
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.$