When SQL Server goes to restore the file, it reads part of the header. In here, the process must detect the DEK and try to decrypt that key. However, since this new instance does not have the certificate, this doesn’t work and an error is thrown, despite not needing the key since the data isn’t encrypted.
The issue here is the DEK still exists in the source database.
Read the whole thing for the solution.