We consider multi-objective simulation optimization (MOSO) problems on integer lattices, that is, nonlinear optimization problems in which multiple simultaneous objective functions can only be observed with stochastic error, e.g., as output from a Monte Carlo simulation model. The solution to a MOSO problem is the efficient set, which is the set of all feasible decision points that map to non-dominated points in the objective space. For problems with two objectives, we propose the R-PERLE algorithm, which stands for Retrospective Partitioned Epsilon-constraint with Relaxed Local Enumeration. R-PERLE is designed for simulation efficiency and provably converges to a local efficient set under appropriate regularity conditions. It uses a retrospective approximation (RA) framework and solves each resulting bi-objective sample-path problem only to an error tolerance commensurate with the sampling error. R-PERLE uses the sub-algorithm RLE to certify it has found a sample-path approximate local efficient set. We also propose R-MinRLE, which is a provably-convergent benchmark algorithm for problems with two or more objectives. R-PERLE performs favorably relative to R-MinRLE and the current state of the art, MO-COMPASS, in our numerical experiments. This work points to a family of RA algorithms for MOSO on integer lattices that employ RLE to certify sample-path approximate local efficient sets, and for which we provide the convergence guarantees.