フーン。じゃあこうか？

(defun pair2 (seq)
(labels ((rec (x xs n)
(if (null x)
n
(let ((n (rec2 x (car xs) (cdr xs) n)))
(rec (car xs) (cdr xs) n))))
(rec2 (e x xs n)
(if (null x)
n
(progn
(format t "(~A ~A)~%" e x)
(rec2 e (car xs) (cdr xs) (1+ n))))))
(format t "~D~%" (rec (car seq) (cdr seq) 0))))

ブツブツ。ほんと世の中 Scheme に毒され過ぎだぜ…。過度の一般化じゃないか？
そりゃ再帰のほうが一般的なのはわかるが、特殊なケースのほうが記述が短い場合に反復を使うのを恐れるべきじゃない。
なんだったら LOOP や DOLIST が再帰で実装されていると思えばいいんじゃないか？