Change SQL Server backup destination while retaining server's knowledge of location
If your retention period for backups is 1 month or something relatively limited, I would suggest the following approach.  


Retain the OLD NAS until the expiry of your retention period for those backups.
Create your directory structure on the NEW NAS and redirect your backups there.
Once your retention period on the OLD NAS expires, then drop use of the OLD NAS.


As you delete old backups the SQL Server will still have the OLD NAS path on the backups that went there.  So it will progressively delete those files without any further action from you.

I generally recommend against updating system tables. 

When we have to move files, we just move them and cope with an extra script to handle the moved files until they are purged.  If you have a week or two on NEW NAS the likelihood of needing the older backups is small.