Em um sistema baseado em RPM:
$ repoquery -l perl-ExtUtils-Embed
lista os arquivos no pacote:
/usr/share/man/man3/ExtUtils::Embed.3pm.gz
/usr/share/perl5/ExtUtils/Embed.pm
Portanto, você está procurando por Embed.pm .
No Ubuntu (que eu acredito estar perto o suficiente do Debian neste caso):
$ apt-file search Embed.pm
procura por pacotes que forneçam o arquivo fornecido, que retorna:
perl-modules: /usr/share/perl/5.18.2/ExtUtils/Embed.pm
Portanto, acredito que você precisa instalar o perl-modules .