矩形範囲に連番を挿入する my-number-rectangle

使い方は、範囲選択して、

3桁で1から開始、1増加
M-x my-number-rectangle RET %03d RET 1 RET
001
002
003
004

3桁で1から開始、10増加
C-u 10 M-x my-number-rectangle RET %03d RET 1 RET
001
011
021
031

16進数の8桁で 128開始、16増加
C-u C-u M-x my-number-rectangle RET %08x RET 128 RET
00000080
00000090
000000a0
000000b0

%03d や %08x 等の書式については format を参照してください。
M-x describe-function RET format RET

my-number-rectangle

(defvar my-number-rectangle-format-history nil
  "History list for `my-number-rectangle'.")
(defvar my-number-rectangle-number nil
  "For internal use.")
(defvar my-number-rectangle-initial-number 1
  "*Default initial number for `my-number-rectangle'.")

(defun my-number-rectangle-read-format ()
  (let (default)
    (if (car my-number-rectangle-format-history)
        (setq default (car my-number-rectangle-format-history))
      (setq default "%03d"))
    (read-string (format "Format of number (default %s): " default)
                 nil 'my-number-rectangle-format-history default)))

(defun my-number-rectangle-line (startcol endcol fmt inc)
  (delete-rectangle-line startcol endcol t)
  (insert (format fmt my-number-rectangle-number))
  (setq my-number-rectangle-number (+ my-number-rectangle-number (or inc 1))))

(defun my-number-rectangle (start end fmt initial-number &optional inc)
  "Replace rectangle contents with numbers on each line.
Number is formatted with a string FMT and starts from INITIAL-NUMBER.
The increment value is 1 unless specified by prefix arg INC.

Example of FMT with number 0 and 31.
%d              \"0\"             \"31\"
% 5d            \"    0\"         \"   31\"
%-5d            \"0    \"         \"31   \"
%+5d            \"   +0\"         \"  +31\"
%05d            \"00000\"         \"00031\"
%x              \"0\"             \"1f\"
%X              \"0\"             \"1F\"
%05x            \"00000\"         \"0001f\"
%#05x           \"00000\"         \"0x01f\"

See `format' for details."
  (interactive
   (progn
     (barf-if-buffer-read-only)
     (unless (and transient-mark-mode mark-active)
       (signal 'mark-inactive nil))
     (let ((fmt (my-number-rectangle-read-format))
           (initial-number (read-number "Initial number: "
                                        my-number-rectangle-initial-number)))
       (list (region-beginning)
             (region-end)
             fmt
             initial-number
             (prefix-numeric-value current-prefix-arg)))))
  (require 'rect)
  (setq my-number-rectangle-number initial-number)
  (apply-on-rectangle 'my-number-rectangle-line start end fmt inc))

;; (global-set-key "\C-xrN" 'my-number-rectangle)

動作確認は GNU Emacs 22 。

wdired でファイル名に連番付ける時に、と思って書いてみたもののあまり使わないですね。
多分他にも似たようなコードは探せば見つかるでしょう。 車輪の再発明をすることで Elisp の経験値は上がっていきます。

余談ですが、GNU Emacs 22 以降の M-x replace-regex はかなり強力です。
行頭に連番挿入する程度ならば
M-x replace-regex RET ^ RET \,(format "%03d" (+ \# 1)) RET
等で十分でしょう。