It is essential to both of these paradoxes that they deal with social situations. Rephrase them so that the agent is interacting with nature, and the paradoxes disappear.

For example, suppose that the parent is instead collecting shells on the beach. He has room in his bag for one more shell, and finds two on the ground that he has no preference between. Clearly, there's no reason he would rather flip a coin to decide between them than just pick one of them up, say, the one on the left.

What this tells me is that you have to be careful using decision theory in social situations, because you have subtle, unspoken values that you can easily forget to take into account. It's fairly obvious in the parent and kids example: she has no preference between them, but she also wants to prove that she has no preference between them, so she flips the coin.

I'm not exactly sure what the social drives are in the first example, though.

Of course this is not different from your own solution, only more specific. As you said,

the parent is allowed to prefer "I threw a coin and my younger child got the car" to "I decided that my younger child would get the car" ... but if so, then these must already be different outcomes.

The presence of a coin flip constitutes a separate outcome, because it matters to her terminal values that her children know that she's not playing favorites.