TL;DR: Move sudo across the pipe (|) to the at command itself.
You haven't really been running at as root.
You ran cat as root (sudo cat ...), and piped the output of cat to at, but you did not run the at command itself as root.
On many systems, some non-root users are permitted to run at jobs. However, if that's not what you want, your system is configured the way you like, and you intend to run this particular at job as root, then you can solve the problem by running at as root instead of cat. (Either way, you do not need to run cat as root in this situation.)
To do that, put sudo before at instead of cat:
cat << EOF | sudo at 'now + 1 minute'
Optional details:
Currently you have:
sudo cat << EOF | at 'now + 1 minute'
echo "hello"
EOF
That runs cat as root with sudo, passing echo "hello" to it (with here-document syntax). The cat command's standard output is piped to the command at 'now + 1 minute', which is not run as root. Therefore at attempts to schedule the job as the non-root user who ran it (you).
If you want the at job to run as root, you can fix this problem by changing it to:
cat << EOF | sudo at 'now + 1 minute'
echo "hello"
EOF
If you later configure a non-root user account that you're using to be permitted to run at jobs, then you would run neither command as root:
cat << EOF | at 'now + 1 minute'
echo "hello"
EOF