Linked Server to Azure Error: "Access to the remote server is denied because no login-mapping exists."
The other answer is wrong and I want to disprove it with repro code and pictures.

The problem here is the parameter @provstr, it's a known issue and how to solve it is described here: Access to the remote server is denied because no login-mapping exists:


  Problem: Unable to run a query through a linked server SQL Server
  2005. This problem only happens with a non-sysadmin account.
  
  You got the message below:
  
  Msg 7416, Level 16, State 2, Line 1 Access to the remote server is
  denied because no login-mapping exists..
  
  Cause: When creating a linked server with the parameter @provstr and
  you use a local SQL Server non-admin or non-Windows account, you have
  to add the parameter "User Name"   into the @provstr
  
  Resolution : Add "User ID=Username" into the provider string on your
  linked server
  
  EXEC master.dbo.sp_addlinkedserver @server = N'LinkServerName',
  @provider=N'SQLNCLI',@srvproduct = 'MS SQL Server',
  @provstr=N'SERVER=serverName\InstanceName;User ID=myUser' 
  
  EXEC master.dbo.sp_addlinkedsrvlogin @rmtsrvname = N'LinkServerName',
  @locallogin = NULL , @useself = N'False', @rmtuser = N'myUser',
  @rmtpassword = N'*****'


The OP has already done it, he included remote login into provider string in the linked server definition, so I really have no idea what else can cause the error.

But now I want to prove that following the cited guide you get rid of the error, while following the other answer we solve nothing.

Here is my repro code.

I have 2 servers, the default and named instance (hp2\sql_2012_dev), I'm going to link hp2\sql_2012_dev server to the default using @provstr without passing in @provstr remote login rmt that is not admin, this will cause the OP's error for ALL non-admin users.

I will map all the local logins to 1 remote login using OP's code.
Then I'll try to apply the suggestion to map the problematic login individually but this will not solve the problem.

Then I'll recreate my linked server passing the remote login with the provider string and this will fix the issue WITHOUT ANY ADDITIONAL INDIVIDUAL MAPPING.

EXEC master.dbo.sp_addlinkedserver 
@server = N'LinkServer2012_rmt', 
@provider=N'SQLNCLI',
@srvproduct = '', 
@provstr=N'SERVER=hp2\sql_2012_dev';--don't pass User ID=rmt' now in order to cause the error

EXEC master.dbo.sp_addlinkedsrvlogin 
@rmtsrvname = N'LinkServer2012_rmt', 
@locallogin = NULL , 
@useself = N'False', 
@rmtuser = N'rmt', 
@rmtpassword = N'*****';


At this point non-admin login l tries to select:

select * 
from linkserver2012_rmt.master.dbo.spt_values; 


And got the error


  Msg 7416, Level 16, State 2, Line 1 Access to the remote server is
  denied because no login-mapping exists.


Ok, we are trying now to map it individually:

EXEC master.dbo.sp_addlinkedsrvlogin 
@rmtsrvname = N'LinkServer2012_rmt', 
@locallogin = N'l', 
@useself = N'False', 
@rmtuser = N'rmt', 
@rmtpassword = N'*****';


And login l re-tries to select from linked server but he's got the same error



At this point I drop and re-create linked server, this time passing in rmt login in linked server definition, and map all the local logins to rmt, without doing any individual mapping:

exec master.dbo.sp_dropserver @server=N'LinkServer2012_rmt', @droplogins='droplogins';

EXEC master.dbo.sp_addlinkedserver 
@server = N'LinkServer2012_rmt', 
@provider=N'SQLNCLI',
@srvproduct = '', 
@provstr=N'SERVER=hp2\sql_2012_dev;User ID=rmt'; --now pass in rmt login 

EXEC master.dbo.sp_addlinkedsrvlogin 
@rmtsrvname = N'LinkServer2012_rmt', 
@locallogin = NULL , 
@useself = N'False', 
@rmtuser = N'rmt', 
@rmtpassword = N'*****';


This time non-admin login l has no problem at all:



I cannot consider this my post a real answer to OP's problem, maybe the cause is Azure and I cannot test it because I have no access to Azure server. But at least it solves the same problem when linking to on-prem instance.

UPDATE

Try to not to use @provstr at all when creating linked server like this:

EXEC sp_addlinkedserver   
   @server=N'LincServer', 
   @srvproduct=N'',
   @provider=N'SQLNCLI', 
   @datasrc=N'myAzureDB.database.windows.net',
   @catalog='MyDB';