Changing email addresses for whole company

A company is going through a rebrand and want to change all of their google based company emails. EG: sales@stackoverflow.co.nz -> sales@stack.co.nz Is there any way this can be changed so they can carry on business as normal without having to tell everyone to use new addresses etc (email must appear to be sent from new domain also).

Thanks for your help not my area of knowledge.