Weight 80% Earth normal: Minor adaptions, less muscle mass needed, perhaps a little taller, maybe thinner bones. Heart has been mentioned, a smaller heart would likely suffice as the muscle demand is smaller. Hemoglobin can only carry so much oxygen so the amount of blood transport should be very similar ignoring the reduced oxygen demand of smaller muscles, blood viscosity would be unchanged, pressure required would be a bit less, so maybe circulation gets a little easier for 2 reasons.
Atmospheric pressure 400% Earth normal: While this heavier atmosphere requires a greater pumping effort, it is also more oxygen rich so perhaps the amount of air pumped could be reduced. Since you pretty much assume a redesign based on optimal changes in a question like this you should expect a change to the response to carbon dioxide. Humans do not have oxygen sensors, they have CO2 sensors. The oxygen starvation sensation is actually a response to elevated CO2 levels. This is why inert gases are dangerous, you don't notice that oxygen is being reduced when displaced by the inert gas. So, either adjust the CO2 sensitivity response or waste energy pumping a lot of air just to keep CO2 level down. Not sure how much tolerance to increasd CO2 is really possible, so this may not really provide a useful optimization if you have to dump CO2 just as much as we do.
Oxygen partial pressure 400% of Earth normal: No problem if you don't mind dying and a lot of painful and debilitating symptoms resulting from oxygen toxicity. before you actually die. Well, that and some other problems too.
In your scenario, you are breathing 0.84 bars worth of oxygen instead of the 0.21 bars we do. Within 90 minutes, many people would be having serious health problems (largely reversible if the source of the problem is corrected). But the long term effects are deeply wired into our biology because of the prevalence of free oxygen radicals, the hydroxyl ion would kill you as it damages vital system like kidneys, lungs, and every other organ since it degrades the lipids in every cell wall. Even bones are damaged by oxygen toxicity.
The body has coping mechanisms for our oxygen levels, but there must be fundamental changes for your scenario. It is commonly held that the oxygenation event a.k.a. oxygen catastrophe is responsible for a major extinction due to oxygen build up over a period a few few thousand to a few ten thousand years. I.e. you really would not have time to evolve sufficient coping mechanisms. Lack of animal life meant that free oxygen was not being removed quickly enough by non-biotic mechanisms to keep many anaerobic species viable. Now assuming humans arrived a few hundred million years after this, the oxygen coping mechanisms would necessarily be present in all animal life (otherwise you die before reproducing).
You may not notice these changes (as they occur at the cellular level) but they would be significant and the body would have to spend a lot of resources on oxidation prevention and cleanup. Cleaning up oxidation damage is already expensive, this would be a dramatic change in resource usage. Probably more redundancy mechanisms as well as more aggressive cleanup methods would be needed. A higher rate of apoptosis would also be a probable outcome. Higher animal forms may not have the margin of error needed to keep functioning -- i.e., sum of resources required for respiration, circulation, digestion, calculation, etc. could exceed the available resources given the added burden if the apoptosis burden increase is large. We operate on a much thinner margin than most people realize. In stressful times, the margins are even thinner. Pregnancy and lactation could be push child bearing into a very marginal outcome zone. Remember that childbirth used to be very dangerous for both the baby and the mother and will be again if would lose modern medicine. Even now, child-bearing is the 6th most common death among women 20-34 in the US.
Perhaps men could share the burden by providing the milk giving the women a change to recover from pregnancy or start another pregnancy before the child is weaned. Lots of social adjustment, but think of this perhaps men could not go topless on the beach instead of women.
Forest fires would also be a huge problem, once started they would be essentially impossible to put out unless you redesign the plant kingdom to be less flammable you will have mega fires.
Plants contains an enzyme RuBisCO that responds strongly to high oxygen levels and happens to be critical to photosynthesis. High oxygen levels can shut down photosynthesis. So you probably need to redesign plants even ignore the fire problem. RuBisCO is and very important and prevalent protein in plants. Designing around the RuBisCO issue may be very difficult.
What about 4 bars atmosphere but only 0.3 bars oxygen?
This is still a pretty rich oxygen environment, forest fires will still be an issue. 0.25 bars O2 is a better choice.
So, you increase the inert gas mix correspondingly. N2 is considered an inert gas in this sense and it would presumably be very likely essentially the remainder of the atmosphere except for some argon, H20, CO2 and trace gases.
For us humans, this presents the problem of nitrogen narcosis. For 3.75 bars of N2 you only get relatively mild narcosis. I could not find any long-term exposure studies and since the clinical basis of inert gas narcosis is murky, I would prefer not to predict the effect of long-term exposure. Since artificial environments are required to induce narcosis I don't think there is much incentive to study long-term exposure.
Since this is only mild level narcosis exposure, I would except that the adaptation would either be mild or non-existent. Maybe a little more computational power in the brain to compensate or scavenging mechanisms in nerve fibers or such-like.
Reduced oxygen levels in hyperbaric environments is how we avoid oxygen toxicity. Such environments are often helium enriched since helium does not cause inert gas narcosis. It is hard to justify a rocky planet having high level of helium in the atmosphere as it is prone to reaching escape velocity. Your lower gravity would accelerate the helium loss, so you are probably stuck with the narcosis unless you could justify a large increase in neon levels. Neon either does not cause narcosis or it is simply considerably smaller effect compared to nitrogen. Xenon is actually worse than nitrogen, you can use an oxygen/xenon atmosphere to replace anesthesia. Xenon is too expensive for this to be practical and you would sound like a Go'auld too.
I can't think of a good way to adapt our lungs, etc. to negate or strongly mitigate the oxygen toxicity problems along the lines commented upon by Ville Niemi. But supposing I'm missing something and it is reasonable, you still need to deal with the other issues with high O2 levels. So overall, 0.25 bars of O2 is probably the best solution - At least it does not cause any major problems that I can think of. Since it is also necessary to solve the other problems from high O2 levels, it seems a much more useful change than trying to make adaptive changes to compensate for oxygen toxicity in humans.
Of course, we also reintroduce the pumping burden problem in full. Since people in good health can already handle this extra burden (though reports of fatigue and soreness are common at first), I would have to say this is not a big problem. A more muscular diaphragm seems pretty easy compared to other changes.