We present a comprehensive abundance analysis of two newly discovered carbon-enhanced metal-poor (CEMP) stars. HE 2138-3336 is a s-process-rich star with Fe/H = -2.79, and has the highest Pb/Fe abundance ratio measured thus far, if non-local thermodynamic equilibrium corrections are included (Pb/Fe = +3.84). HE 2258-6358, with Fe/H = -2.67, exhibits enrichments in both s- and r-process elements. These stars were selected from a sample of candidate metal-poor stars from the Hamburg/ESO objective-prism survey, and followed up with medium-resolution (R ~ 2000) spectroscopy with GEMINI/GMOS. We report here on derived abundances (or limits) for a total of 34 elements in each star, based on high-resolution (R ~ 30,000) spectroscopy obtained with Magellan-Clay/MIKE. Our results are compared to predictions from new theoretical asymptotic giant branch (AGB) nucleosynthesis models of 1.3 M sub(middot in circle) with Fe/H = -2.5 and -2.8, as well as to a set of AGB models of 1.0 to 6.0 M sub(middot in circle) at Fe/H = -2.3. The agreement with the model predictions suggests that the neutron-capture material in HE 2138-3336 originated from mass transfer from a binary companion star that previously went through the AGB phase, whereas for HE 2258-6358, an additional process has to be taken into account to explain its abundance pattern. We find that a narrow range of progenitor masses (1.0 < or =, slant M(M sub(middot in circle)) < or =, slant 1.3) and metallicities (-2.8 < or =, slant Fe/H < or =, slant -2.5) yield the best agreement with our observed elemental abundance patterns.