For 2D elastic-plastic flows with the hypo-elastic constitutive model and von Mises' yielding condition, the non-conservative character of the hypo-elastic constitutive model and the von Mises' yielding condition make the construction of the solution to the Riemann problem a challenging task. In this paper, we first analyze the wave structure of the Riemann problem and develop accordingly a Four-Rarefaction wave approximate Riemann Solver with Elastic waves (FRRSE). In the construction of FRRSE one needs to use an iterative method. A direct iteration procedure for four variables is complex and computationally expensive. In order to simplify the solution procedure we develop an iteration based on two nested iterations upon two variables, and our iteration method is simple in implementation and efficient. Based on FRRSE as a building block, we propose a 2nd-order cell-centered Lagrangian numerical scheme. Numerical results with smooth solutions show that the scheme is of second-order accuracy. Moreover, a number of numerical experiments with shock and rarefaction waves demonstrate the scheme is essentially non-oscillatory and appears to be convergent. For shock waves the present scheme has comparable accuracy to that of the scheme developed by Maire et al., while it is more accurate in resolving rarefaction waves.