The seventh seeded Indo-Czech pair was beaten 4-6, 6-7(5) in 89 minutes.
Paes and Stepanek, the US Open winners, now have to beat Marcel Granollers and Mark Lopez to make it to the next stage without any favour from the other teams.
They had beaten Alexander Peya and Bruno Soares in their opening match on Tuesday.
Following Wednesday’s victory, their second in as many matches, Marrero and Verdasco became the first team to qualify for the semi-finals.
The top two teams in each group qualify for the semi-finals.
Marrero and Verdasco mixed net and baseline play to negotiate a break of Stepanek’s serve to 30 for a 5-4 lead in the first set, Verdasco clinching the 34-minute opener with a hold to love by finishing with an ace.
Paes dropped his serve to 30 in the opening game of the second set, but the Indian-Czech team recovered from 0-2 by winning three straight games.
Both teams completed routine service holds as the set went to the tie-break.
Verdasco served for the set at 6-4, but hit a double fault. His second serve hit Marrero on the shoulder and both players turned to one another and smiled.
Marrero sealed victory on their second match-point when he hit a powerful forehand to the feet of Paes.
Image: David Marrero (left) and Fernando Verdasco of Spain celebrate victory in their men's doubles match against Leander Paes of India and Radek Stepanek of the Czech Republic
Photograph: Clive Brunskill/Getty Images
Paes-Stepanek make winning start at World Tour finals
Paes, Sania in semi-finals of China Open
Paes and Czech-mates a winning combo
PHOTOS: For ever-smiling Paes age is just a number
Rankings: Yuki up to 204 in singles; Paes in 9th spot in doubles