Formal security of recycled random blinding in a Paillier scheme
You have to worry not just about a pair of blinding values being equal, but more complex relationships between them.  Thus, finding a proof of security for this approach looks non-trivial to me.

Let me elaborate.  Suppose $R_j$ is the $j$th blinding variable you use.  If $R_i = R_j$, that's a problem, but as you say, that can be made very unlikely.  However, that's not the only potential problem.  If there exist indices $a,b,c,d$ such that $R_a R_b = R_c R_d$, then you might also have a problem, and this happens with higher problem.  At least, this will be a difficulty for a proof of security, as this relationship is detectable by an adversary and allows some kinds of distinguishing attacks.  If you make $k$ and $n$ large enough, you can rule out even this kind of multiplicative relationship, but you might still have to worry about higher-order multiplicative relationships, and it's not entirely clear to me how you'd address this challenge.

Perhaps you can deal with this somehow and prove something with some additional insights, but I think the above phenomenom will be a non-trivial complication.



You subsequently revised the question to propose a proof strategy.  Your revised proof strategy won't work.  It requires showing that there's unlikely to be a collision between products of the $R$'s.  However,  you won't be able to show that, because it's not true: if you consider products of very large size, it's overwhelmingly likely that some such collision does exist.  You can't avoid that by choosing $k$ and $n$ to be larger.  So, the proof strategy you suggest in the revised question isn't going to work.  This is more delicate than you might have realized, and it's not clear to me how to prove that your idea is secure (or whether a proof is possible).