Depends on what you are trying to achieve out of Automating a test: 

1. Is it need based automation? E.g. -
you can not run the test/observe the test results accurately in a non-automated manner. It is a very controlled test environment.

 Here the question of "when" does not arise. You just have to take a call whether to automate a test or not.

2. Is the time based automation? E.g. - regression tests.
Generally these are the ideal candidates for automation and that usually takes place when the functionality has 'matured', when you have a safe level of confidence in the stability of future (including a risk analysis of visible changes). 

 For such candidates, firstly, automation is easier to develop ,tests are more reliable(false failures are less probable) and you can concentrate on "new" functionalities to test.