For $1 \leq i \leq n$, let $A=\begin{bmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \cdots & a_{nn} \\ \end{bmatrix}$, $B_i=\begin{bmatrix} b_{i1} \\ \vdots \\ b_{in} \end{bmatrix}$ and $C_i=\begin{bmatrix} c_{i1} \\ \vdots \\ c_{in} \end{bmatrix}^*$.
Let $D=A+\sum_{1 \leq i \leq n}B_i k_i C_i$. Then, for almost all $a_{ij}$, $b_{ij}$, $c_{ij}$, there exists $k_i \in \mathbb{C}$ such that all eigenvalues of $D$ are zeros.
The variety $N$ of nilpotent matrices has codimension $n$ (e.g., this MSE answer). In projective space, generally, $A,B_1C_1,B_2C_2,\dotsc,B_nC_n$ span an $n$-plane. Because of the dimension, this plane meets $N$. So there is some combination $k_0 A + k_1 B_1 C_1 + \dotsb + k_n B_n C_n$ which is nilpotent, with not all of the $k_i$ equal to zero.
Generally an $(n-1)$-plane misses $N$. If the plane spanned by the $B_i C_i$ (without $A$) misses $N$, then it forces $k_0$ in the above linear combination to be nonzero. Dividing by $k_0$ gives $A + k'_1 B_1 C_1 + \dotsb + k'_n B_n C_n$ nilpotent.
So, does the $(n-1)$-plane spanned by the $B_iC_i$ miss $N$? It's not quite a general $(n-1)$-plane because it's spanned by rank one matrices. But it still misses $N$ anyway. The family of $(n-1)$-planes spanned by rank one matrices is irreducible, so it's sufficient to show a single one that misses $N$. Take the rank one matrices with a $1$ in one position on the diagonal and all other entries zero. These are rank one, linearly independent, and no linear combination of them is nilpotent.
[update] By an example of 4x4-matrices the ansatz below could not be used to solve the problem. The matrix $\small Q_K $ cannot in general be made lower triangular by choices of the $\small k_i $. I'll delete this answer soon if I cannot improve the ansatz.
a) There is a similarity transformation with a rotation T such that $\small P = T^{-1}\cdot A \cdot T = T' \cdot A \cdot T $ where P is triangular and has the eigenvalues of A on its diagonal.
b) Your sum-expression of vector outer products, let it be called matrix $\small E_K = \sum_{i=1}^n B_i k_i C_i = \sum_{i=1}^n k_i (B_i C_i)= \sum_{i=1}^n k_i E_i $ is a weighted (by the $\small k_i $ weights) sum of rank-1-matrices $\small E_i $
From the "similarity rotated version" of all matrices
$\qquad \small Q_K = T' E_K T = \sum_{i=1}^n k_i (T' E_i T) = \sum_{i=1}^n k_i Q_i $ (which should be made triangular by choices of $\small k_i $ ) and
$\qquad \small R = T' D T $ which is then also triangular
we get your final equation in its form with triangular matrices
$\qquad \small R = P + Q_K $
We'll have a solution if the weights $\small k_i $ for the non-triangular, generic but rank-1-matrices $\small Q_i $ can be chosen such that their sum $\small Q_K$ becomes triangular and its diagonal equals the negative diagonal in $\small P $.
I've a vague speculation that the equation with this triangular matrices can easier be shown to be "almost always" possible, but have not yet a further concrete approach. At least this construction exhibits that the rank-1-matrices $\small E_i $ (and thus $\small Q_i$ ) cannot be simple scalar multiples of each other if A has full rank and thus the restriction to "for almost all" is unavoidable and possibly mainly consists of this property.
