I can't come up with a solution that uses only sed, but this comes close. It uses only sed, shell builtins, and cmp and mv. With some effort and a modern shell, you could rewrite this to use shell builtins and not have to use cmp or mv.

#!/bin/sh
if test $# -ne 1
then
    echo usage: $0 file
    exit 1
fi
num=1    # start numbering at 1
infile="$1"
outfile="$1.out"
mv "$infile" "$outfile"    # set up so initial cmp always fails
while ! cmp -s "$infile" "$outfile" # repeat the sed until no more ^* can be found
do
    mv "$outfile" "$infile"
    # replace the first occurrence of ^* with a number and a space
    sed '0,/^\*/s//'$num' /' "$infile" > "$outfile" 
    num=$(expr $num + 1)
done
rm "$outfile"

test:

$ cat i
first line
*second
*third
fourth
*fifth
$ ./change i
$ cat i
first line
1 second
2 third
fourth
3 fifth

I can't come up with a solution that uses only sed, but this comes close. It uses only sed, shell builtins, and cmp and mv. With some effort and a modern shell, you could rewrite this to hold the file contents in shell variables, and not have to use cmp or mv.

#!/bin/sh
if test $# -ne 1
then
    echo usage: $0 file
    exit 1
fi
num=1    # start numbering at 1
infile="$1"
outfile="$1.out"
mv "$infile" "$outfile"    # set up so initial cmp always fails
while ! cmp -s "$infile" "$outfile" # repeat the sed until no more ^* can be found
do
    mv "$outfile" "$infile"
    # replace the first occurrence of ^* with a number and a space
    sed '0,/^\*/s//'$num' /' "$infile" > "$outfile" 
    num=$(expr $num + 1)
done
rm "$outfile"

test:

$ cat i
first line
*second
*third
fourth
*fifth
$ ./change i
$ cat i
first line
1 second
2 third
fourth
3 fifth