Fuel production from hydrogen and carbon dioxide is considered an attractive solution as long-term storage of electric energy and as temporary storage of carbon dioxide. A large variety of CO2 sources are suitable for Carbon Capture Utilization (CCU), and the process energy intensity depends on the separation technology and, ultimately, on the CO2 concentration in the flue gas. Since the carbon capture process emits more CO2 than the expected demand for CO2 utilization, the most sustainable CO2 sources must be selected. This work aimed at modeling a Power-to-Gas (PtG) plant and assessing the most suitable carbon sources from a Life Cycle Assessment (LCA) perspective. The PtG plant was supplied by electricity from a 2030 scenario for Italian electricity generation. The plant impacts were assessed using data from the ecoinvent database version 3.5, for different CO2 sources (e.g., air, cement, iron, and steel plants). A detailed discussion on how to handle multi-functionality was also carried out. The results showed that capturing CO2 from hydrogen production plants and integrated pulp and paper mills led to the lowest impacts concerning all investigated indicators. The choice of how to handle multi-functional activities had a crucial impact on the assessment.