This one was tough. Googling showed that this problem could be solved by uncommenting the line '$ModLoad imklog' in /etc/rsyslog.conf. This in turn caused kern.log to be filled with messages like 'imklog: error reading kernel log - shutting down: Bad file descriptor'. This in turn is probably caused by some strange interaction between Ubuntu and OpenVZ/virtualization combination, but initially I did not find the precise cause of the problem, nor a solution.
This link finally gives a clue what the problem is and also presents a working workaround:
Following the solution worked for me. In more detail:
Create file /etc/init/kmsg-pipe.conf with the following content:
# Ye Olde /proc/kmsg hack by Mike Gogulski
# from http://www.nostate.com/4228/fixing-the-100-cpu-and-no-useful-output-imklogrsyslog-kernel-logging-problem-on-ubuntu-guests-under-xen-pv
# This is free and unencumbered software released into the public domain under # the terms of the Unlicense [http://unlicense.org/].
description "/proc/kmsg pipe hack for rsyslogd"
start on started rsyslog
stop on stopped rsyslog
mkdir -p /var/run/rsyslogd || true
mkfifo /var/run/rsyslogd/kmsg || true
chown -R syslog /var/run/rsyslogd || true
chmod -R 700 /var/run/rsyslogd || true
exec dd bs=1 if=/proc/kmsg of=/var/run/rsyslogd/kmsg
This effectively creates a shadow copy of /proc/kmsg (using dd and a named pipe) which is accessible by the syslog user.
Then adapt /etc/rsyslog.conf to use this:
echo '$KLogPath /var/run/rsyslogd/kmsg' >> /etc/rsyslog.conf
Then execute the script and restart rsyslogd:
initctl start kmsg-pipe
service rsyslog restart
Now /var/log/kern.log should show kernel messages, for example iptables LOG output.