This article investigates second order intertwinings between semigroups of birth-death processes and discrete gradients on the space of natural integers N. It goes one step beyond a recent work of Chafa{ï} and Joulin which establishes and applies to the analysis of birth-death semigroups a first order intertwining. Similarly to the first order relation, the second order intertwining involves birth-death and Feynman-Kac semigroups and weighted gradients on N, and can be seen as a second derivative relation. As our main application, we provide new quantitative bounds on the Stein factors of discrete distributions. To illustrate the relevance of this approach, we also derive approximation results for the mixture of Poisson and geometric laws.