Las dos frases pueden tener significados distintos: si lo que se expresa es una obligación, no ha de emplearse la preposición de (se debió pagar); si lo que se expresa es una conjetura, puede utilizarse o no, aunque lo más habitual es hacerlo (se debió de pagar).