Modifying existing templates is one of the cases where simply modifying the template is easier than using a plugin -- but it is possible to do with a plugin, and since it doesn't involve modifying existing code, upgrades etc. can be easier.
To do this, you'll need to check Request::getRequestedPage() and Request::getRequestedOp() to make sure you're dealing with a page that you want to modify. If so, use Smarty's postfilter mechanism to register an output filter that watches for the "Start a New Submission" link and, if it's found, appends another link.
If you'd like an example that uses postfilters, have a look at the rounded corners plugin (plugins/generic/roundedCorners). This plugin is a little more complicated than what you'll be doing.
Another option you have is to drop some hooks of your own into OJS templates and write a template that uses them. This does involve modifying the template code, but this is a good way of keeping a logical separation between OJS and your own modifications.
Public Knowledge Project Team