Doing the math and explaining that downward forces are needed to produce upward acceleration, etc. is absolutely correct; even tho the numbers change depending on how, and how high, he throws them. One might be tempted to suggest he could throw them very gently upward ... this approach fails, but more math is needed to prove it.
Throwing them "very gently upward" will not work - it does not change the amount of force needed - just the amount of time the watermelons spend in the air. Think of it this way: if he just stands there with a watermelon in his hand, he exerts 80kg down force (79 for himself, 1 for the watermelon). To move the watermelon upward - at any speed - requires additional force be exerted downward, exceeding the 80kg limit and collapsing the bridge.
(In reality, kgs are not a unit of force. The bridge is capable of supporting 80kg x 9.8N/kg = 784 Newtons of force. The man exerts 774.2N and the watermelon exerts 9.8N. We can just stick with kgs for simplicity)... unless ... the bridge is so short he can toss them into the air before getting on the bridge -- and catch them after he has finished crossing it.
I like that solution. I had thought about horizontal juggling (yes, it exists - I do it myself). Basically, think of regular juggling of three items, but reduce the height. Keep reducing it until the majority of the force used in throwing the ball is along the horizontal plane rather than vertical. At this point you are juggling very quickly, but with very little upward force. Unless the bridge has really bad horizontal stability, this would allow juggling to get the melons across. But to do this with watermelons would be extremely difficult. And he must still walk very slowly, so as not to exert more than 9.8N while lifting his body weight or placing his foot. That would be unlikely.
I wonder if he could bowl the watermelons across and then walk? I guess that depends on the length of the bridge.
I say that he should walk downriver to a bridge that has been properly constructed, get is watermelons across, then call the newspaper to report on the shoddy construction practices, lack of inspections and obvious safety concerns raised by his recent ordeal. Someone should be doing jail-time over this!