Concentrated suspensions of soft deformable particles, e. g., polymer microgel pastes and compressed emulsions, display a generic slip behavior [Meeker et al., J. Rheol. 92, 18302 (2004a); Meeker et al., J. Rheol. 48, 1295-1320 (2004b)]. When sheared with smooth surfaces, they exhibit apparent motion due to slip at the wall. Wall-slip stops at a sliding yield stress the value of which is much lower than the bulk yield stress. The physical mechanism of slip at low stresses and the origin of the sliding yield stress have so far been unresolved issues. We propose that the paste-wall interactions control the wall-slip behavior and determine the occurrence of the sliding yield point. We present experiments performed with different shearing surfaces. Two distinct slip behaviors are identified: depending on whether the interaction between the microgel particles and the wall is attractive or repulsive, wall-slip can be either suppressed or promoted. We provide an extension to the elastohydrodynamic slip model of Meeker and co-workers by incorporating attractive or repulsive interactions between the slipping paste particle and the wall. The interplay of various short range forces due to van der Waals, hydrophobic/hydrophilic, and/or electrostatic interactions and elastohydrodynamics is used to explain the influence of the shearing surface on wall-slip. The model encompasses the different slip regimes observed in our experiments and can predict the slip behavior accurately for well characterized surfaces. (C) 2008 The Society of Rheology.