When should automation begin?

Automation is almost always a good way to go for testing. Manual testing is still important, but it's much more error-prone, and if your manual testing process begins to take days or weeks to complete, it becomes difficult to roll out updates at a fast rate. It's usually easier to setup automation at the beginning of a project, because you'll have fewer things to automate, and once you get your automation framework in place, it should be easy to expand as your project grows.

Trying to automate testing on an already fully-implemented project will probably require more work than automating from the beginning, so I'd recommend diving in as soon as possible.

You automate because pressing "go" and waiting 10min for the results means that your tester can do other useful work during those 10min instead of baby-sitting the application.

Keep in mind that an automated test can run every night while you sleep. Your testers can then use their working hours to write new useful tests instead of running the same old tests over and over again.

The biggest reason is that when you changed some little thing shortly before shipping, with automated tests you won't hesitate to run the tests even though "the change was simple and shouldn't have broken anything" - and then you breathe a sigh of relief when the automated tests catch the bug you had introduced and were about to ship.

I think it depends on the people working at the company. Some people love automation, some are less fond of it. If your company doesn't have it by now trying to implement it could be difficult.

I prefer automation, because of the hours (mentioned already) and because for the most part you know what you are going to get with it.

You should have both, but to go without automation and test will get very difficult as product grows.