BACKUP CERTIFICATE TestCert only backs up the certificate, not anything it protects.

I then deleted the symmetrical key

The key is now gone, you cannot recover it, nor can you recover any data you encrypted. Throw it all out and start again.

CREATE SYMMETRIC KEY TestSymKey
WITH ALGORITHM = AES_256
ENCRYPTION BY CERTIFICATE TestCert;

That just creates a new key, protected by the now restored old certificate. The certificate and key are unrelated, except for the fact that the key is now being encrypted and protected by the certificate.

What you need is to backup the key.

BACKUP SYMMETRIC KEY TestSymKey
 TO FILE = N'c:\Backup\TestCert.cer'
 ENCRYPTION BY PASSWORD = N'AReallyStr0ngK#y4You';

Then restore it

RESTORE SYMMETRIC KEY TestSymKey
 FROM FILE = N'c:\Backup\TestCert.cer'
 DECRYPTION BY PASSWORD = N'AReallyStr0ngK#y4You';

Do note that unfortunately you cannot protect the key backup with teh certificate. Instead a password must be used, which encrypts with 3DES, a weak encryption.

An alternative is to recreate the symmetric key using the same parameters. For that, you need to know the source. SO change your original CREATE to:

CREATE SYMMETRIC KEY TestSymKey
WITH
  ALGORITHM = AES_256,
  KEY_SOURCE = 'ReallyStrongPasswordHere',
  IDENTITY_VALUE = 'id_phrase'
ENCRYPTION BY CERTIFICATE TestCert;

Now to recreate it, just execute the same statement on the new server. It must be the same version of SQL Server.

One final note: if you backup/restore the database itself then the certificate and key will be backed up also.

BACKUP CERTIFICATE TestCert only backs up the certificate, not anything it protects.

I then deleted the symmetrical key

The key is now gone, you cannot recover it, nor can you recover any data you encrypted. Throw it all out and start again.

CREATE SYMMETRIC KEY TestSymKey
WITH ALGORITHM = AES_256
ENCRYPTION BY CERTIFICATE TestCert;

That just creates a new key, protected by the now restored old certificate. The certificate and key are unrelated, except for the fact that the key is now being encrypted and protected by the certificate.

What you need is to backup the key.

BACKUP SYMMETRIC KEY TestSymKey
 TO FILE = N'c:\Backup\TestCert.cer'
 ENCRYPTION BY PASSWORD = N'AReallyStr0ngK#y4You';

Then restore it

RESTORE SYMMETRIC KEY TestSymKey
 FROM FILE = N'c:\Backup\TestCert.cer'
 DECRYPTION BY PASSWORD = N'AReallyStr0ngK#y4You';

Do note that unfortunately you cannot protect the key backup with the certificate. Instead a password must be used, which encrypts with 3DES, a weak encryption.

An alternative is to recreate the symmetric key using the same parameters. For that, you need to know the source. So change your original CREATE to:

CREATE SYMMETRIC KEY TestSymKey
WITH
  ALGORITHM = AES_256,
  KEY_SOURCE = 'ReallyStrongPasswordHere',
  IDENTITY_VALUE = 'id_phrase'
ENCRYPTION BY CERTIFICATE TestCert;

Now to recreate it, just execute the same statement on the new server. It must be the same version of SQL Server.

One final note: if you backup/restore the database itself then the certificate and key will be backed up also.