I didn't know you could use a ContextMenu as a region - you learn something new every day!
Anyway, try the following:-
<ContextMenu>
<regions:RegionManager.RegionName>
<MultiBinding StringFormat="{}{0}-{1}">
<Binding Path="DeviceHolderRegion" />
<Binding Path="DeviceHolder.ID" />
</MultiBinding>
</regions:RegionManager.RegionName>
</ContextMenu>
I haven't tried running it, but VS XAML editor doesn't complain about the syntax, which is a promising start.