Emissions of toxic heavy metals (HMs), as Hg, As, Cd, Pb, etc., and some harmful compounds of F, Se, and B are related to waste streams from coal-fired power plants (CFPP). Coal/lignite combustion, due to relatively high content of ash, sulfur, and chlorine, generates in flue gas cleaning processes tremendous amount of fly ash, CaSO4 and CaCl2. Measures for minimization of Hg- and NOx-emissions (e.g. addition of bromides and NH3) change properties of fly ash, wastewater and speciation/partition of HMs. Wet flue gas desulfurization (FGD) consumes high amount of fresh water and generates harmful wastewater with water soluble salts. The planned, more stringent limits on emissions of dust, Hg, HCl, HF, SO2, etc. in CFPP will increase contents of polluting compounds in solid and liquid waste streams. We critically assess possibilities, measures and obstacles for higher efficiency of Hg and HMs removal from flue gas in CFPP, together with efficient removal of other pollutants including mutual influences and interrelations. The fates of mercury, selected harmful HMs, and some other pollutants in waste streams from wet FGD are critically analyzed and discussed. Non-toxic, stable forms of mercury (e.g. HgS) and other HMs in solid waste should be preferred. Schemes and measures for minimization of emissions and hazardous waste streams from air pollution control (APC) are compared and discussed for three selected technologies of coal combustion with different methods of gas cleaning.