Can Ruined Rex's Deathknell target Ruin Runner or Baron Nashor?

No. Ruin Runner and Baron Nashor cannot be targeted. "Deal 4 damage to an enemy unit" still requires choosing a target — it does not fall into the exception for effects where the affected object is fixed. Some effects do not target because what they affect is set in stone, but this one needs a choice.