When starting this question I was very hesitant - literature on the subject is vast and I thought most likely the answer is already there somewhere.
Then when the list "Questions that may already have your answer" appeared, the first on the list was Constructing Markov traces simply which is from March 2012 and has no answer, and this encouraged me to go ahead and ask:
There are famous Markov traces on (group algebras of) braid groups, providing knot/link invariants and much more, and constructed via similar traces on finite-dimensional algebras like Birman-Wenzl/Kaufmann, Iwahori-Hecke, Temperley-Lieb algebras etc.
The question is the most naïve one - can these traces be realized as plain ordinary traces of matrices in linear representations of algebras in any of these cases?