Изменение цвета View из ViewModel

Можно ли это реализовать "более красиво" без string?

Можно. Вы не должны устанавливать цвета из VM, это задача представления.

Например. У вас чат, вы хотите выделить входящие сообщения голубым, а исходящие - зеленым цветом, вы не должны в VM определять свойство цвет и устанавливать его. Вы должны просто выставить свойство Direction, которое будет иметь некий ваш тип, или может enum, или, на худой конец, bool. А в V вы просто привязываетесь к этому свойству и преобразовываете его в цвет с помощью конвертера:

enum Direction { Incoming, Outgoing }
class MainVM : Vm
{
    Direction direction;
    public Direction Direction
    {
        get => direction;
        set => Set(ref direction, value);
    }
}

Я использую такую базу для конвертера, она позволяет упростить написание конвертеров и разметку:

abstract class ConverterBase : MarkupExtension, IValueConverter
{
    public abstract object Convert(object value, Type targetType, object parameter, CultureInfo culture);
    public virtual object ConvertBack(object value, Type targetType, object parameter, CultureInfo culture)
        => throw new NotImplementedException();
    public override object ProvideValue(IServiceProvider serviceProvider) => this;
}

Сам конвертер, может выглядеть как-то так:

class MessageDirectionToBrushConverter : ConverterBase
{
    public override object Convert(object value, Type targetType, object parameter, CultureInfo culture)
    {
        var direction = (Direction)value;
        var color = direction == Direction.Incoming
                  ? Colors.LightBlue
                  : Colors.LightGreen;
        return new SolidColorBrush(color);
    }
}

Если такой конвертер потребуется в нескольких местах - его можно параметризировать.

Использование:

<Rectangle Fill="{Binding Direction,
    Converter={local:MessageDirectionToBrushConverter}}"/>

Обратите внимание, конвертер возвращает значение типа SolidColorBrush (которое наследуется от Brush), а не Color, так как заливка элементов задается именно кистью. Как раз именно по этому не работает ваш код (если опустить корректность использования паттерна MVVM).

Во-первых, ваш VM-класс должен реализовать INotifyPropertyChanged. Тогда изменения в VM будут подхватываться и во View.

Затем, вы не показываете ваш код, а значит, не исключена ошибка в привязке. Перепроверьте!

Ну и наконец, с точки зрения MVVM установка цвета — не задача VM, VM не должна заниматься визуальными свойствами. Найдите семантику, смысл, который стоит за сменой цвета, и выставьте как свойство её. А цвет из ней получайте через триггер или конвертер.

Пример с триггерами (используем базовый класс VM отсюда):

class SignalVM : VM // реализует INotifyPropertyChanged
{
    bool haveSignal;
    public bool HaveSignal
    {
        get => haveSignal;
        set => Set(ref haveSignal, value);
    }
}

Разметка:

<Grid>
    <Grid.Style>
        <Style TargetType="Grid">
            <Setter Property="Background" Value="Green"/>
            <Style.Triggers>
                <DataTrigger Binding="{Binding HaveSignal}">
                    <DataTrigger.Value>
                        <sys:Boolean>False</sys:Boolean>
                    </DataTrigger.Value>
                    <DataTrigger.Setters>
                        <Setter Property="Background" Value="Red"/>
                    </DataTrigger.Setters>
                </DataTrigger>
            </Style.Triggers>
        </Style>
    </Grid.Style>
</Grid>

Вам понадобится объявить xmlns:sys="clr-namespace:System;assembly=mscorlib". Вместо Grid можно взять, понятно, любой другой элемент.