I have not seen any specific design guidelines on legends when it comes to tables, but I assume it would be similar to how you should style legends on charts and graphs.
The known design patterns for dealing with some of the interactions that will remove the need for the legend include:
- creating a toggle/button to switch between view and editing modes where only the editable cells will change state (or you can actually just vary the style of the cell to make the editable ones look like input fields)
- creating a hover-over effect (i.e. tool-tip) where the icons are displayed (I assume that you are doing this anyway?)
- creating columns specific for different statuses (e.g. override applied) so you don't need to apply styling to the entire row
You may need to try a combination of the above strategies (including your own solution) to see what works best with the data to be displayed and test with end users, but I think the design patterns I mentioned seemed to be more common than using a legend in a table.
I want to point out that the rationale you mentioned for not wanting to end up with 'an army of pencils' could be the same with having lots of rows with missing data resulting in 'an army of exclamation points'.
Just keep in mind that as long as you don't intend to introduce too much more variation or types of content to the table, all you need to do is make sure that design decisions are consistent and simple. That way at least the users will be able to learn it quickly and get used to the design.