In the context of growing sustainability demands, businesses are increasingly adapting their production practices by integrating remanufacturing. However, companies often face challenges in profitably implementing remanufacturing due to complexities arising from uncertainties in processes, product quality, and market conditions. This highlights the need for effective decision support in remanufacturing processes. Addressing this challenge, our research introduces an algorithm designed to identify cost-efficient process plans that optimize order fulfillment while considering a company’s specific capabilities and inventory levels. By modeling the remanufacturing planning process as a Markov process, our algorithm comprehensively accounts for both process-related and quality-related uncertainties. This approach enables the evaluation of all Pareto optimal process plans in terms of cost efficiency and reliability. We validate our methodology through a real-world application in the automation industry, specifically focusing on the remanufacturing of variable speed drives. This case study demonstrates the practical relevance of our approach and a potential for significant cost reductions, enhanced process efficiency, and improved labor productivity. Overall, businesses gain critical insights into the financial prospects of their remanufacturing efforts, identifying opportunities for optimization and expansion into new product quality categories. This enhances their economic potential and aligns with consumer preferences for distinct product qualities.