Coal remains an important energy source. Nonetheless, pollutant emissions - in particular Oxides of Nitrogen (NOx) - as a result of the combustion process in a boiler, are subject to strict legislation due to their damaging effects on the environment. Optimising combustion parameters to achieve a lower NOx emission often results in combustion inefficiency measured with the proportion of unburned coal content (UBC). Consequently there is a range of solutions that trade-off efficiency for emissions. Generally, an analytical model for NOx emission or UBC is unavailable, and therefore data-driven models are used to optimise this multi-objective problem. We introduce the use of Gaussian process models to capture the uncertainties in NOx and UBC predictions arising from measurement error and data scarcity. A novel evolutionary multi-objective search algorithm is used to discover the probabilistic trade-off front between NOx and UBC, and we describe a new procedure for selecting parameters yielding the desired performance. We discuss the variation of operating parameters along the trade-off front. We give a novel algorithm for discovering the optimal trade-off for all load demands simultaneously. The methods are demonstrated on data collected from a boiler in Jianbi power plant, China, and we show that a wide range of solutions trading-off NOx and efficiency may be efficiently located.