Likely, this is due to the directory being backed up doesn't have "read" permission. Check to make sure the folder is set to "755" if the folder is owned by a user different than PHP runs as.
No. After extensive testing it's been shown that Suhosin causes numerous conflicts especially in terms of execution time.
To get around this you have a couple options. Your best option would be to take backups from the Console or Command Line. When ran from the Console, PHP doesn't have any limits like time or memory; it just goes and goes until it's done.
If that's not possible, you'll have to increase your max_execution_time setting in PHP. I can't give you a value to set, since it's dependent on how many files, how large those files are, the CPU and RAM available, and I kid you not, the type of hard drive on your server (SSD vs the old spinning disk variety), so you may have to experiment. Were it me, I'd start at 30 minutes and work my way down.
And, if setting PHP configuration isn't an option, you'll have to get fancy with configuration. For example, be explicit about what directories to backup. Avoid using the exclude paths if possible. Definitely don't use regular expressions for excluding paths (that takes TONS of time).