Sort Rows by Attributes

Apologies I didn't realise you needed those in the sort as well - thought it was just by the Clearance one from the description. In that case, I can't see why there would be any issue with what you first did, i.e.

= Table.Sort(#"Removed Errors",{{"Location", Order.Ascending},{"Building", Order.Ascending},{"Employee Name", Order.Ascending},{"Clearance Sort Order", Order.Ascending}}))

My supicion is that you may have made a mistake in the formula that Pete suggested, as that's the only place I can see an issue. Eitherways, in case you can't find a solution with that I might suggest another approach in that you could load the data 'as is' (i.e. without sorting) from Power Query into the Model (i.e. hitting "Close and Apply") and then going to the "Table View" (picture shown below) and creating a DAX expression based on the idea that Pete suggested, and doing the sort in the Table View based on that DAX expression - this is what matters at the end of the day anyways, as its closer to the 'Front-end". 

Hopefully one of the suggestions works out for you