Computational thinking (CT) is a fundamental skill and an analytical ability that children in the twenty-first century should develop. Students should begin to work with algorithmic problem-solving and computational methods in K-12. Drawing on a conceptual framework (IGGIA) that combines CT and problem-solving, this study designed and implemented an interdisciplinary Scratch course in a primary school, examined the impact of the new problem-solving instructional approach (the adapted IGGIA) on pupils' CT skills and self-efficacy, and explored the gender differences in these two aspects. A pretest-posttest nonequivalent group design was conducted among 63 fifth-grade students in two computer science classes over 14 weeks. Both quantitative and qualitative data were collected through the administration of CT scales, Scratch artifacts analysis and focus group interviews. The results revealed that the adapted IGGIA: (1) significantly improved the CT skills of primary school students; (2) had a significant positive impact on pupils' CT self-efficacy, especially on their critical thinking, algorithmic thinking and problem-solving; and (3) significantly enhanced girls' CT skills and self-efficacy. These findings indicated that problem-solving instructional approaches could promote both cognitive and noncognitive aspects of students' deeper computational learning.