How can I mark all packages with installed dependents as "Automatically Installed"?

You could use Aptitude's why command:

for x in $(apt-mark showmanual)
do
  r="$(echo ${x} | sed -e 's/\([+.]\)/[\1]/g')"
  aptitude why ${x} | egrep -q "^i.* (Pre)?Depends +${r}( |$)" && apt-mark auto ${x}
done

Not tested, because it's not something I want to (have to un-)do on my machine.