You have wrong TXT-record:
Use value TXT-record:

v=DKIM1; k=rsa; p=MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQDWdCBmsPYub6KXNdiuntRwQJ8y LLh1viv3YLeoNW7ayPDHXFpR3O1pcU3fHQimhSBH67KXpH7oWAfka09GRUCh7UBm iEbjldlrTXdX7QBr4Ff70vRIhBogkwN8rRPlF+c69lRkrALJp6psOD4D1Gwx58kZ LDQrM19qwVH+SKIaBQIDAQAB

You put your conifg in /etc/exim4/conf.d/transport/00exim4-configheader which assumes that you are using split configuration. By default, when setting up Exim (at least on Ubuntu) “<No>” is selected when asked “Split configuration into small files?”. If you went with the defaults, then you should add you config options to /etc/exim4/exim4.conf.localmacros.

This was exactly my problem. I followed a guide that had me create /etc/exim4/conf.d/main/00_config_dkimoptions and after updating the config and restarting Exim, it still was not signing. Eventually, I found a post on Server Fault (Exim4 doesn’t add DKIM signatures) and realized my problem.

I looked at the output form:

exim -bV

Which pointed me to /var/lib/exim4/config.autogenerated. There I found this:

#########
# WARNING WARNING WARNING
# WARNING WARNING WARNING
# WARNING WARNING WARNING
# WARNING WARNING WARNING
# WARNING WARNING WARNING
# This file was generated dynamically from
# non-split config (/etc/exim4/exim4.conf.localmacros
# and /etc/exim4/exim4.conf.template).
# The config files are supplemented with package installation/configuration
# settings managed by debconf. This data is stored in
# /etc/exim4/update-exim4.conf.conf
# Any changes you make here will be lost.
# See /usr/share/doc/exim4-base/README.Debian.gz and update-exim4.conf(8)
# for instructions of customization.
# WARNING WARNING WARNING
# WARNING WARNING WARNING
# WARNING WARNING WARNING
# WARNING WARNING WARNING
# WARNING WARNING WARNING
#########

Since /etc/exim4/exim4.conf.localmacros didn’t exist, I just copied the config to that new file:

sudo cp /etc/exim4/conf.d/main/00_config_dkimoptions /etc/exim4/exim4.conf.localmacros

Now, after applying those updates:

sudo update-exim4.conf
sudo service exim4 restart

IT WORKS!!

Basically, here is everything I did:

SELECTOR=`date +%Y%m%d%H%M%S`
DOMAIN=example.com

openssl genrsa -out ${SELECTOR}._domainkey.${DOMAIN}-private.pem 1024 -outform PEM
openssl rsa -in ${SELECTOR}._domainkey.${DOMAIN}-private.pem -out ${SELECTOR}._domainkey.${DOMAIN}.pem -pubout -outform PEM

sudo mkdir -p /etc/exim4/dkim/
sudo cp ${SELECTOR}._domainkey.${DOMAIN}* /etc/exim4/dkim/

sudo tee -a /etc/exim4/conf.d/main/00_config_dkimoptions > /dev/null <<EOF
DKIM_CANON = relaxed
DKIM_SELECTOR = ${SELECTOR}
DKIM_DOMAIN = ${DOMAIN}
DKIM_FILE = /etc/exim4/dkim/${SELECTOR}._domainkey.${DOMAIN}-private.pem
DKIM_SIGN_HEADERS = true
DKIM_PRIVATE_KEY = ${if exists{DKIM_FILE}{DKIM_FILE}{0}}
EOF

cat /etc/exim4/conf.d/main/00_config_dkimoptions | sudo tee -a /etc/exim4/exim4.conf.localmacros > /dev/null

sudo update-exim4.conf
sudo service exim4 restart

Also, make sure that your DNS matches:

${SELECTOR}._domainkey IN TXT "k=rsa; p=$(cat /etc/exim4/dkim/${SELECTOR}._domainkey.${DOMAIN}.pem | sed 's/^-.*-$//' | tr '\n' ',' | sed 's/,//g')"