MacOS – Time Machine wants to decrypt the backup volume

The only solution I can offer is to use Disk Utility to create an encrypted sparsebundle, then copy the contents of the existing backup disk into the sparsebundle. This is essentially what Time Machine does.

Then, select a new backup disk in Time Machine and select the sparsebundle. If all works according to plan, Time Machine will ask for your password and begin using the new sparsebundle.

Try to use tmutil inheritbackup:

sudo tmutil inheritbackup /Volumes/Data/OldHostname.sparsebundle

From man tmutil:

inheritbackup {machine_directory | sparsebundle}
        Claim a machine directory or sparsebundle for use by the current
        machine. Requires root privileges.

        Machine directories and sparsebundles are owned by one computer
        at a time, and are tracked by unique identifiers rather than com-
        puter name, host name, or ethernet address. The inheritbackup
        verb reassigns the identity of the specified item, reconfiguring
        it so the current host recognizes it during backups. When inher-
        iting a sparsebundle, the machine directory within will also be
        claimed.

        Inheriting is typically only one step in the process of configur-
        ing a backup for use by a machine. You may also need to use
        setdestination, associatedisk, or both, depending on the situa-
        tion.

        One machine can own multiple machine directories and sparsebun-
        dles, but it is ill-advised for them to reside in the same place.
        In such a situation, which will be chosen during a backup is
        undefined. As a result, inheritbackup will attempt to detect pos-
        sible identity collisions before making changes.

See also http://pondini.org/TM/B6.html.