Have you read over my algae page at
http://www.fishpondinfo.com/algae2.htmIt sounds like some attached algae or hair algae is growing in the falls. It is helping to filter the water for you so it's not all bad. You can plant some plants in the falls like watercress (see
http://www.fishpondinfo.com/plant3.htm) to compete with the algae and filter the water. Also, if you block some light to the falls, less algae will grow. Adding plants helps to do that but other things can create shade as well.
How big is the actual pond? Is it big enough for koi? The plecos can't eat the algae in the falls because I assume that they can't get there. Keep an eye on the plecos in case they decide to suck on the goldfish or koi.