Bottom aeration's only purpose is to live up to it's name; aerate the bottom of the pond by creating a vertically rotating current of water which will continuously expose new water to the pond surface to be oxygenated by natural gas transfer. If you are looking to remove 'Muck', the pond should be dredged by a professional. Removing muck the way you described will only cause erosion of the bottom which will eventually advance to the edges of the pond causing collapse.
Most any marginal plants will work. Try to put in a good diversity. Stay away from the common Cattail!!!
Your test results still have me baffled. Algae feeds on Nitrates. Your test results show "0" Nitrates. How can you have algae? It's like growing a vegetable garden in the barren desert without any fertilizer. It can't be done. If you have algae, you have Nitrates at a fairly decent level. The more algae you have the higher the Nitrates. The only other possibility would be that you have a high Phosphate level. Have you observed any 'Foaming' around the base of the waterfall. This is usually a sign of Phosphates.
I can't suggest an algaecide because I don't use them.