The paradox of willpower is both simple and complex, ha ha.
Simple
We are motivated to complete tasks.
We sometimes don't complete tasks we have motivation for.
We often complete tasks we apparently have less motivation for.
Complex
Let's bracket everything else in those sentences above and analyse motivation.
Motivation and willpower are linked. Willpower is the ability to maintain a course of action to achieve an effect we desire. Motivation is the desire.
Motivation can be categorised as intrinsic and extrinsic based on the factors that cause the desire.
Intrinsic motivation comes from within ourselves, e.g. "I want to train my body to be able to do things I like".
Extrinsic motivation comes from outside ourselves, e.g. "I want to train my body because other people would find me more attractive.
You may have noticed that the intrinsic/extrinsic distinction is abstract, artificial, and easily disrupted. Therefore it is only true to a certain extent. However, it is true enough for the purpose of an attempt to understand the paradox of willpower.
The work of Senay et al, 2010 illustrates this paradox and the means of overcoming it quite beautifully. To summarise, the researchers found that training volunteers to prime their minds through self-talk into a more open, questioning state enabled them to perform better at certain tasks. This effect was contrasted with groups of other volunteers who had been primed with tasks intended to increase willpower and motivation. The latter group performed measurably worse. In the second phase of the experiment the latter group demonstrated a focus on extrinsic motivation, while the former group who had been primed into the more "open, questioning" state demonstrated a focus on intrinsic motivation.
The priming tasks used by the researchers involved the different use of a repeated phrase, a mantra. "I will" was significantly outperformed by "Will I?".