Cruel Patron

I play Cruel Patron, and I have a 1 [M] Recruit alone at a battlefield I control. I choose to kill my Recruit to pay the additional cost of Cruel Patron. Although this causes a cleanup, because there is an item on the chain (Cruel Patron) I don’t lose control of the battlefield. I can choose to play Cruel Patron to that same battlefield with no issue.

Q: If I play Cruel Patron and kill one of my units for its additional cost, but one of these cards replaces that unit’s death, does the cost still count as paid?

Yes. You made the decision to pay the cost and took the action to pay it. What happened after that doesn’t matter.