I had an unbelievably good tofu steak in a restaurant in Tokyo many years ago. I have never been able to reproduce it.
It tasted uncannily like a beef steak.
What sauce / spices could I use to mimic the steak flavour?
I don't know anything about cooking tofu, so this is purely addressing the beef flavor part. If you want to make something bland taste more like beef, one the largest issues is going to be adding umami flavor. It is present to some degrees in meats, cheeses, mushrooms, soy sauce, and tomatoes. I'd start with a sauce containing several of these items, and then add some complementary flavors (peppers, citrus, sugar, etc).
The "tofu steak" I know of in Japan (豆腐ステーキ) is generally not vegetarian. However, there are a number of variations that could be adapted in that direction.
Most versions I've seen start with momen-doufu (medium firm, but this is often softer than tofu with that description in the US). A marinade is highly unlikely. Often, the tofu will be grilled on a hot griddle, sometimes with a dusting of cornstarch, katakuriko, or flour, which can create a charred aroma that will be reminiscent of steak. Sometimes roasted sesame oil is used to augment this perception, but keep in mind that it has a low smoke point.
The tofu will either be topped with or briefly simmered with some sauce, often consisting of some combination of shimeji, enoki or other Japanese mushrooms, and ground pork, simmered in katsuo-dashi (dried skipjack-tuna based soup stock) usually with some additional starch. Leeks or shallots may be added. Generally, there's some soy sauce, mirin (sweetened shochu or sweetened rice wine), and sugar added to this mix. Pork and mushrooms aren't present in all versions of this dish, but one or the other is common. Other than black pepper and salt, it's unlikely that any uncommon spices would be used. I would expect that a somewhat heavy-handed use of freshly ground black pepper will be closest to what you seem to be looking for. Some people might add a touch of butter to the sauce (and by some people, I mean me).
The soup stock is important (for umami and aroma); if you want a vegetarian alternative, consider simmering dried porcini and kelp gently for a while after soaking.
There are a ton of variations of this basic set of steps will give you some place to start that's at least somewhat in line with Japanese conventions. It's quite possible the restaurant you went to did things differently, of course.
Tofu comes in different grades depending on their water content, firmness, and texture. Silk tofu is great for smoothies but won't hold up to cooking in a pan or on a grill. Hard or firm tofu is, as it sounds, more rigid and easiest to keep solid. You might get the best results from a medium grade that has some of the smoothness of silk but enough of the structure of firm. Also, firmer tofu will take on flavor better than silk, since the silk type is so fine that it's virtually impenetrable as a solid.
Wrap the tofu in paper towels and press under a plate for 5-10 minutes. Then marinate the tofu like you would a barbecue dish. Put it in the fridge for 2-3 hours (or 20-30 minutes) before cooking. Teriyaki sauce would work great. Barbecue sauce might be nice. Any combination of soy sauce, honey, lime juice, sesame oil, fish sauce, red pepper, black pepper, garlic, salt... you really can't go wrong. Just don't forget that tofu has virtually no flavor except what you put in/on it.
Take the tofu out (a few minutes ahead wouldn't hurt). Use a knife to wipe off excess marinade, and pat dry with a towel again to enhance browning. Heat some oil in a pan and carefully put the tofu slab into it. You want it around medium-high, since that will brown the tofu but not require constant flipping to avoid burning. Leave it for 2-3 minutes, then carefully flip it over. A bigger spatula will be helpful. Brown the other side, using your leftover marinade to glaze the tofu, and pouring the rest into the pan to reduce into a sauce. Pull the tofu after 2-3 minutes, leaving the sauce to reduce further if necessary.
Let the tofu sit for a few minutes to cool.
Serve with whatever complements your seasoning: sauteed onions/mushrooms/toasted ground peanuts...