SSDT Schema Comparison for Stored Procedure signed by a Certificate
Before getting into any specifics about Certificate creation and module signing, we can at least verify whether or not the two instances have the same certificate. Run the following on both instances:

SELECT [thumbprint], [cert_serial_number], [sid],
       [issuer_name], [subject],
       [expiry_date], [start_date]
FROM   sys.certificates
WHERE  [name] = N'cert_name';


If the Certificates are the same, then all of those fields will have identical values across both instances (or both databases on the same instance). But you mainly just need to check the thumbprint field since it is an SHA-1 hash of the certificate. If that value is different between the two locations, then you aren't dealing with the same certificate.



You say that


  the Certificate was created in each instance from the same script


but do not mention exactly how the Certificates are being created. They can be generated in SQL Server (this is known as "self-signed") by using the following syntax:

CREATE CERTIFICATE [cert_name]
  ENCRYPTION BY PASSWORD = 'certpassword' -- this is optional but best to use
  WITH SUBJECT = 'cert_subject';


This method will generate a new private key (each time it is run) and encrypt that with the password specified in the ENCRYPTION BY PASSWORD clause else encrypted by the database master key (which is why it is better to specify the password).

Or, you can create them by providing an existing Assembly, File, or Binary literal:

CREATE CERTIFICATE [cert_name]
FROM
   ASSEMBLY assembly_name
 | EXECUTABLE FILE = 'path_to_DLL'
 | FILE = 'path_to_file'
   WITH PRIVATE KEY ( FILE = 'path_to_private_key' )
 | BINARY = 0x......
   WITH PRIVATE KEY ( BINARY = 0x..... )


The FILE and BINARY methods allow for optionally specifying a private key file or binary literal. So if using one of those methods along with specifying the private key, or if using the signed ASSEMBLY, then creating a certificate this way should provide you with the same private key each time.

So how do you get the FILE or BINARY values?


FILE:  

Once you have created the initial Certificate, export it (including the private key!) using the following:

BACKUP CERTIFICATE [cert_name]
  TO FILE = 'path\to\cert_file.cer' 
  WITH PRIVATE KEY
  (
    DECRYPTION BY PASSWORD = 'cert_password',
    FILE = 'path\to\key_file.pvk',
    ENCRYPTION BY PASSWORD = 'file_password'
  );


And in the new place:

CREATE CERTIFICATE [cert_name]
  FROM FILE = 'path\to\cert_file.cer'
  WITH PRIVATE KEY
  (
    FILE = 'path\to\key_file.pvk',
    DECRYPTION BY PASSWORD = 'file_password',
    ENCRYPTION BY PASSWORD = 'cert_password'
  );

BINARY: (only available in SQL Server 2012 and newer)  

Once you have created the initial Certificate, get the certificate and private key values using the following:

SELECT CERTENCODED(CERT_ID('cert_name')) AS [CertificateBinary],
       CERTPRIVATEKEY(
                      CERT_ID('cert_name'),
                      'temp_password',
                      'cert_password'
                     ) AS [PrivateKeyBinary];


And in the new place:

CREATE CERTIFICATE [cert_name]
  FROM BINARY = 0x{CertificateBinary}
  WITH PRIVATE KEY
  (
    BINARY = 0x{PrivateKeyBinary},
    DECRYPTION BY PASSWORD = 'temp_password',
    ENCRYPTION BY PASSWORD = 'cert_password'
  );



If you are using SQL Server 2012 or newer, then the BINARY method would be the easiest since it is completely self-contained (i.e. doesn't rely upon any external files).

PLEASE NOTE:  


Regardless of which method above is chosen, the initial Certificate creation only needs to happen once, and probably needs to be done manually so that the backup file(s) or binary literals can be incorporated into the SSDT project.
If the private key is being used for creating the Certificate in the target database, then there is no need for the WITH SIGNATURE clause of ADD SIGNATURE since it is only used when the private key was removed or not used in the creation of the Certificate.
In this case (i.e. all of those fields in sys.certificates matching and using the private key in the CREATE CERTIFICATE), signing modules in two different locations that have the exact same definition (as in: byte-by-byte the same), will produce the same signature
If the private key is not being used for creating the Certificate, or has been removed (yes, you can do that), then you need to specify the WITH SIGNATURE clause and pass in the binary literal of the signature that was generated by the same private key and same module definition from a location that at least at one point did have the private key.
This is a more secure set up because it only allows for signing modules that you provide the signatures for. If a Certificate does not have a private key, it can still be used to check the validity of signed modules, but it cannot be used to sign new or changed modules (which is kinda cool).




BUT, if:


the Certificates in both locations are identical, and
the schema compare didn't flag the module definitions as being different, and
ADD SIGNATURE is being used in the destination database using the WITH SIGNATURE clause,
the binary literal being used is the same as found in the source database via:

SELECT OBJECT_NAME(major_id), crypt_property
FROM   sys.crypt_properties;



then you need to check the OBJECT_DEFINITION for that module in both locations. They need to be identical, including casing, etc. You can do a SELECT CONVERT(VARBINARY(MAX), OBJECT_DEFINITION(OBJECT_ID(N'{module_name}'))) just to be sure. It is possible that the schema comparison is ignoring differences in comments and/or the casing of the CREATE keyword at the beginning of the definition and/or some white-space, etc.



Please see the following MSDN pages for details:


CREATE CERTIFICATE
BACKUP CERTIFICATE
CERTENCODED
CERTPRIVATEKEY
CERT_ID
ADD SIGNATURE
sys.certificates
sys.crypt_properties