Justin, are you saying your laser budget is $5K? If so, you've got LOTS of good choices, a 50 watt fiber for one. I've got a OLM3 which is a 10 watt diode and it does pretty good. Take a look thru this thread to get some good ideas. https://knifedogs.com/threads/the-laser-thread.53963/
If you're only planning on using it for makers mark and you have a 5K budget, I'd suggest looking into the best fiber laser you can get for your money. That will give you the best quality, deep mark.
That said, I use a 10Watt diode laser that ran in the 800-900 range and I am happy with the quality of the maker's mark I am able to get with this modest machine.
I use a C02 laser and marking fluid. While it does not engrave down into the steel, the marking fluid penetrates the steel into the pores. I can tell you by experience that you will have to grind out the mark if you mess it up.....
i have not tried paint. We use Brilliance marking fluid. It's for laser engraving. I hear folks also use Cerramark, but it's more expensive... (none of it's cheap)