We have $k_{\mathbb{C}}(n)=k(n)=\frac12n(n-1)$ for all $n > 2$ (for $n=2$, we have $k_{\mathbb{C}}(2)=1$, $k(2)=0$).
First, I'll show that these are upper bounds before showing that they can be attained. I'll use the fact that a smooth map from an $m$ dimensional manifold (or finite union of $m$ dimensional manifolds) to an $n$ dimensional manifold cannot be onto unless $n\le m$.
It was noted in the question that $k(n)\le\frac12n(n-1)$, so I'll just look at the complex case.
The space ${\rm U}(n)$ of $n\times n$ unitary matrices has dimension $n^2$, and the space ${\rm GL}_{\mathbb{C}}(n)$ of complex $n\times n$ matrices has dimension $2n^2$. If $U$ is unitary such that $U^HAU$ has $k$ zero entries, then $V^HAV$ also has $k$ zero entries, where $V=DU$ for a diagonal unitary matrix $D$. For example, it is always possible to choose $D$ such that the first nonzero element of each row of $V$ is real. Letting $R$ be the space of $n\times n$ unitary matrices whose first nonzero element in each row is real, this has dimension $n(n-1)$. Letting $S$ be the $n\times n$ complex matrices with at least $k$ zero entries, this has dimension $2(n^2-k)$. We require the map $R\times S\to {\rm GL}_{\mathbb{C}}(n)$, $(U,M)\mapsto UMU^H$ to be onto. So,
$$
{\rm dim}(R\times S)=n(n-1)+2(n^2-k)\ge{\rm dim}(GL_{\mathbb{C}}(n))=2n^2,
$$
so, again, $k\le\frac12n(n-1)$.
Now, we can prove the lower bound. It was noted in the question that $k_{\mathbb{C}}\ge\frac12n(n-1)$, as all complex matrices can be put in upper triangular form by a Schur decomposition. So, only the real case remains. For positive integers $n_1+n_2+\cdots+n_m=n$, we can express an $n\times n$ matrix $A$ in block form
$$
A=\pmatrix{
A_{11} & A_{12} &\cdots&&A_{1m}\\
A_{21}&A_{22}&\cdots&&A_{2m}\\
\vdots&&\ddots&&\vdots\\
\\
A_{m1}&A_{m2}&\cdots&& A_{mm}
}
$$
where $A_{ij}$ is an $n_i\times n_j$ real matrix. As noted by Omnomnomnom, using the real Schur form, then replacing $A$ by $Q^TAQ$ for orthogonal $Q$, this can be done so that it is block upper triangular ($A_{ij}=0$ for $i > j$) and such that each $n_i$ is 1 or 2. We can take $n_1=n_2=\cdots=n_r=2$ and $n_{r+1}=n_{r+2}=\cdots=n_m=1$ (where $r\in\{0,1,\ldots,m\}$ is the number of complex-conjugate pairs of eigenvalues of $A$). The nonzero below diagonal terms of $A$ then correspond to the below diagonal terms of the block diagonal elements $A_{ii}$. There are $r$ of these, so $A$ has at least $\frac12n(n-1)-r$ zero entries below the diagonal. We cannot remove these remaining $r$ below-diagonal nonzero entries, but we can introduce an additional $r$ zeros above the diagonal. Note first that if $Q$ is a real matrix in block form $Q=(Q_{ij})_{i,j=1,\ldots,n}$ with $Q_{ij}=0$ for $i\not=j$ (i.e., block-diagonal) with each $Q_{ii}$ orthogonal, then $Q$ is orthogonal. Furthermore, $B=Q^TAQ$ has block form $B=(B_{ij})$ with $B_{ij}=Q_{ii}^TA_{ij}Q_{jj}$. So, $B$ is also block upper triangular.
(1) For any $k < m$ with $n_k=2$, there is an orthogonal block-diagonal matrix $Q$ such that $B=Q^TAQ$ has block entries $B_{ij}=A_{ij}$ for $i,j\not=k$ and $B_{km}$ has a zero entry.
To show this, let $v\in\mathbb{R}^2$ be the first column of $A_{km}$ and $R$ be a $2\times2$ rotation matrix with $R^Tv=(\lVert v\rVert,0)^T$. Then, $R^TA_{km}$ is upper triangular and letting $Q$ be the block-diagonal matrix with $Q_{kk}=R$ and all other block diagonal elements being the identity gives the result.
As long as $r < m$ or, equivalently, $A$ has at least one real eigenvalue, we can apply this so that $A_{rm}$ has a zero entry, then so that $A_{r-1,m}$ has a zero entry, and so on to end up with each $A_{im}$ having a zero entry for $i\le r$. If $r=m$ or, equivalently, $A$
has no real eigenvalues, we can use the following.
(2) If $i < j$ is such that $n_i=n_j=2$ then there exists an orthogonal block-diagonal matrix $Q$ such that $B=Q^TAQ$ has block entry $B_{ij}$ being diagonal.
By the singular value decomposition, there exists $2\times2$ orthogonal matrices $R,S$ with $R^TA_{ij}S$ being diagonal. Then, letting $Q$ be the block-diagonal matrix with $Q_{ii}=R$, $Q_{jj}=S$ and all other diagonal entries being the identity gives the result.
Now in the case where $n > 2$ and $A$ has all complex eigenvalues (so $r=m\ge2$), we can apply (2) to make $A_{r-1,r}$ diagonal so that it has two zero entries. Iteratively applying (1) with $i=r-2,r-3,\ldots$ introduces a zero entry in each of the blocks $A_{im}$ for $i\le r-2$. This puts $A$ into upper block triangular form with $r$ zeros above the diagonal.