My idea is to have a shared folder on the domain server, then create symbolic links to the NAS folders, depending on the user only certain folders will show.
This would not work out with a Windows server, nearly all Microsoft services do impersonation (i.e. they pass the authentication claim provided by the client through to the destination). You might be able to get that running with a Samba host, though - there you could set up AD integration and just use a single proxy account to access the NAS. Keep in mind that you are adding another point of failure, though, you might want to explore all other options first.
Is it possible to setup symbolic links to an external source with credentials supplied?
No. You could try using the
/SAVECRED parameter with an initial
net use for each of your potential NAS users, but it has the downside of excessive manual work (you would need to enter the username and the password into the security dialog manually, there is no way to script this). Also, clients seem to occasionally "forget" the saved auth information, which makes it pretty much useless for most use cases where you would expect robust access.
Windows clients would try NTLMv2 authentication against the server by default. This means they would send a username and a challenge response mangled through the secret password's hash. If you create users on your NAS whose usernames correspond to the AD usernames and set the passwords to the according users' passwords, you should be able to access the NAS without seeing any authentication request dialogs.
Of course this would be a nightmare to manage if your user list or their passwords are rapidly-changing, also you would need to know the user's passwords, which is not always an option. And again, there might be a lot of manual work if you have a large number of users and cannot script user creation on the NAS.
An alternative approach might be to create a handful of users on your NAS with known passwords and use
net use \\NAS\share /user:nasuser /password:<secret> calls in logon scripts for domain users which would need access to the NAS resources. Note that as your domain users generally do have read rights for the logon scripts, you are exposing the NAS passwords to them in plain text using this approach.