SQL Server can't directly change a string to a binary, so its asking that you convert the data. With respect to Code First Migrations, I would drop the AlterColumn statements from the DbMigration, and instead manually write:
AddColumn("dbo.TableName", "ColumnNameTmp", c => c.Binary());
Sql("Update dbo.TableName SET ColumnNameTmp = Convert(varbinary, ColumnName)");
DropColumn("dbo.TableName", "ColumnName");
RenameColumn("dbo.TableName", "ColumnNameTmp", "ColumnName")
And the reverse in the Down method, if desired. (the above is pseudocode, forgive any syntax errors)