I have not seen any specific design guidelines for table legends, but I guess it would look like how you should style captions on charts and graphs.
Design patterns known to address some of the interactions that will eliminate the need for the legend are:
- create a toggle button to toggle between view and edit modes where only editable cells will change state (or you can simply change the cell style so that editable elements look like input fields)
- create a hover effect (tooltip) where the icons are displayed (I suppose you do it anyway?)
- creating specific columns for different statuses (for example, applied substitution), so you do not need to apply style to the entire line
You may need to try a combination of the above strategies (including your own solution) to see what works best with the data to display and test it with the end users, but I think the design patterns that I'm using I mentioned seemed to be more common legend in a chart.
I would like to point out that the reason you mentioned for not wanting to end up with "an army of pencils" could be the same thing: having a lot of lines with missing data giving rise to "an army of dots." exclamation".
Just keep in mind that as long as you do not intend to introduce too many variations or types of content into the table, all you have to do is to ensure that design decisions are consistent and simple. In this way, users will at least learn quickly and get used to the design.