SQL Server: what additional permissions for EXECUTE for implicit result codes?
What has happened here is that you have inadvertently included the GRANT statement in your stored procedure definition.

Most people assume that the BEGIN/END block contains the definition of the stored procedure, but it is actually through the end of the batch in which the CREATE PROCEDURE statement is executed (i.e.: the next GO or the end of the script, whichever comes first.)

In my experience, it is common to omit a GO between the stored procedure definition and the following GRANT statements in build scripts. I've done it myself! And it often goes unnoticed because a lot of people run their apps with db_owner role membership, and db_owner can execute the GRANT with no problem.

So, simply remove the GRANT from the procedure definition, and handle permissions in a separate batch or script:

CREATE PROCEDURE [dbo].[sp_fakeProcedureName] 
AS
BEGIN
  SET NOCOUNT ON;

  SELECT    fakeTablePKIdentity, column2, column3, column4 
  FROM fakeTable
  ORDER BY column2
END
GO