Tente isto:
:%s,\(<a href='#footnote-\d\+'>\)\d\+\(</a>\),*,g
Para dividir:
% - Operar sobre o arquivo inteiro (este é um intervalo especial)
,...,..., - Normalmente, o delimitador para: substituto é /, mas pode ser qualquer coisa. Eu usei vírgulas por causa do < / a > tag.
\(...\) - Cria uma subexpressão, para uso no padrão de substituição. Dois deles são usados.
\d\+ - Corresponde a qualquer dígito, e o \+ faz com que ele corresponda a um ou mais.
/ - No padrão de substituição, é substituído pelo primeiro. e a segunda subexpressão mencionada anteriormente.
g - O sinalizador "g" após um padrão de substituição diz operar globalmente em cada linha, e não apenas na primeira partida em uma linha.
Tudo isso e mais é explicado em :help pattern.txt , mas isso pode ser esmagador. Existe um livro chamado "Mastering Regular Expressions" que pode ser útil.