(defun once-only-expansion (bindings)
  (loop for (name form) in bindings
        for gensym = (gensym)
        collect name into names
        collect (list gensym form) into form->gensym
        collect (list name gensym) into gensym->name
        finally (return (values names
                                (append form->gensym gensym->name)))))

(defmacro foo (bindings &body body)
  (multiple-value-bind (names bindings)
      (once-only-expansion bindings)
    `(let* (,@bindings)
       (flet (,@(loop for name in names
                      collect `(,name (&rest args) (apply ,name args))))
         ,@body))))