Столбец HeaderTemplate является сгенерированной управляющей частью DataGrid и не имеет прямого доступа VisualTree к DataContext DataGrid, поэтому необходимо добавить RelativeSource AncestorType и явно обратиться к свойству через DataContext
"{Binding DataContext.AllSelected, RelativeSource={RelativeSource AncestorType=Window}}" />
или вы также можете написать это верхнему элементу в шаблоне
DataContext="{Binding DataContext, RelativeSource={RelativeSource AncestorType=DataGrid}}"