Using the Decorator Pattern to Conditionally Replace Behaviour Instead of Extending

Initially I had this structure:

interface IFileBackup
{
    void Backup();
}

class BackUpMechanism1 : IFileBackup
{
    void Backup()
    {
        //Back it up
    }
}

class BackUpMechanism2 : IFileBackup
{
    void Backup()
    {
        //Back it up in another way
    }
}

class Client 
{
    //Instantiation of both mechanisms
    //

    try
    {
        backUpMechanism1.Backup();
    }
    catch(Exception ex)
    {
        backupMechanism2.Backup();
    }
}

I was told that this was not a very clean design and to redesign it using the decorator pattern. The client should not know about the two back up mechanisms but just call backup and then the first mechanism should try to back up the file and if that fails then use mechanism 2. However I don't understand how to use the decorator pattern because from my understanding it extends functionality but doesn't replace functionality - which is what I want... How do I archive that? I have tried the following:

interface IFileBackup
{
    void Backup();
}

class BackupMechanism1 : IFileBackup
{
    public void Backup()
    {
        try
        {
            Console.WriteLine("Trying to back up to the cloud...");
            throw new Exception();
        }
        catch(Exception ex)
        {
            Console.WriteLine("Oops that failed. We need to back up locally instead...");
        }

    }
}

class BackupMechanism2 : IFileBackup
{
    IFileBackup _fileBackup;
    public BackupMechanism2(IFileBackup fileBackup)
    {
        _filebackup = fileBackup;
    }

    public void Backup()
    {
        //All examples I have seen does this. But doesn't make sense in my case?
        _fileBackup.Backup();

        Console.WriteLine("Backing up locally");
    }
}

//The client does not care about how the backup is done
class Client
{
    static void Main()
    {
        //This is not right, but not sure what I should do in the client.
        BackupMechanism2 localBackup = new BackupMechanism2(new BackupMechanism1());
        localBackup.Backup();

        Console.Read();
    }
}

So essentially what I want to achieve is to have two backup mechanisms. Have the client just say backup I don't care how. Let the first mechanism try it's backup method if that fails then try the second method. I'm trying to use the decorator pattern to extend(replace) the backup behaviour of the first mechanism if it fails. I'm struggling to come up with a design that makes sense.