If you say:
EXECUTE [Linkserver].[DatabaseName].[dbo].[stored procedure]
And you get the error
Msg 2812, Level 16, State 62, Line 1
Could not find stored procedure "DatabaseName.StoredProcedure".
(There is a disconnect between command and error message; "dbo" is missing from the error message. I will have to assume that this is because you have modified the statement and the message manually for this post.)
The normal interpretation of this error is that there is no procedure with this name in a database by this name on the linked server. It could be that you have a typo in any of the names, so check that first. Next check that the database really exists on the linked server. If it does, you need to talk with someone responsible for the database about the stored procedure.
Alternatively, you do not have permission to access the database or the stored procedure in question. Or the login on the remote server that your login maps to does not have permission.
As for "It looks like stored procedure is not linked to linked server.", there is no such concept, once you have connected to the linked server, it is the same as you have connected directly to that server through SSMS or an application. The call to sp_addlinkedserver is for a linked server that runs a completely different product than SQL Server and has no relevance here.