Você terá que escapar do * as \* . O * é especial em expressões regulares e significa que corresponde ao anterior zero ou mais vezes .
A substituição no Vim seria
:%s/(\*,\*)//g
Se você cancelar a opção magic no Vim, com
:set nomagic
então somente os caracteres ^ ("início da linha") e $ ("fim da linha") têm um significado especial nas expressões regulares.
Isso significa que a substituição
:%s/(*,*)//g
faria o que você gostaria de fazer.
A maioria das pessoas deseja ter a opção magic definida (e é configurada por padrão no Vim).