Here’s a very simple proposal:
Every transaction must include a “total fee” in its body. The Plasma chain operator only accepts transactions if their total fee exceeds that of their parent tx, and prioritizes by total_fee - parent_total_fee. When a coin is withdrawn, the amount that can be withdrawn is equal to deposit_size - total_fee.
Though this certainly would ruin nice clean exact-denomination coins.
Another missing alternative here is transaction fees through channel payments.