Seu problema com a expressão regular é sua ganância (os quantificadores * e + tentam corresponder o máximo possível). Infelizmente, não há como informar sed para usar expressões regulares não-vorazes . Você tem que usar Perl para conseguir isso, embora haja soluções alternativas para sed .
Então, experimente o seguinte Perl one-liner :
perl -pe 's/\(.*?\)(, )?//g' /var/log/apt-history.log
Isso deve manipular o texto como você deseja. Você encontrará o PCRE (expressões regulares Perl) muito semelhante ao POSIX / GNU BRE e ERE um sed usa.