A polymer-carbon sorbent for removing at least one of carbon dioxide, heavy metals or toxic materials from a flue gas from a combustion process, such as coal-fired power plants, is described. The sorbent comprises a carbonaceous sorbent material and a cured amine-containing polymer, and sulfur. The polymer-carbon sorbents are formed by curing a curable amine-containing polymer in the presence of the carbonaceous sorbent material, sulfur, a cure accelerator and, optionally, a cure activator. A convenient carbonaceous sorbent material is an activated carbon, and a convenient curable amine-containing polymer is an allyl-containing poly(ethyleneimine), having a number average molecular weight between about 1,000 and about 10,000. The polymer-carbon sorbents may contain sulfur in molar excess of an amount needed to cure the curable amine-containing polymer. Such polymer-carbon sorbents are shown to capture more mercury, in both elemental an ionic forms, compared to activated carbon and adsorb carbon dioxide.