How to change "Add new node" button label?
I suggest you take a small form_alter sample module code and start changing in it. Pl also see this video.

You can also do it easily using String Overrides module.