Carbon capture and utilization (CCU) can be a pertinent solution to avoid millions of tons of carbon emission. The challenge is to identify, among numerous available options of carbon sources capture/utilization technologies, and products, the CCU pathways with best economic and/or CO2 reduction potential. In this work, we propose a novel framework for identifying sustainable CCU pathways, i.e., combinations of sources, processes, and products, using a superstructure based on state-task network (STN) representation. STN allows incorporation of nonlinear models including first-principles or surrogate models into the superstructure representation of potential CCU pathways. The proposed framework solves the superstructure optimization problem of mixed-integer nonlinear programming (MINLP) by introducing logic-based outer approximation (LOA), to reduce the computational time and improve the solvability greatly. A case study using a sizable CCU superstructure demonstrates that LOA can reduce the computational time from hours to minutes while identifying any sustainable pathway from a superstructure with highly nonlinear surrogate models.