Matching is a separate but important topic. Matching will encourage employees to contribute money to get the match.
Small companies have 401Ks. They do it to attract potential employees. I or my spouse have have worked for four small companies, three had 401K programs. Two didn't match and I believe that they struggled to get employees to participate. The other had a match and almost everybody participated.
There are costs to run them. Management will have to investigate the fixed costs, and the costs of annual fees based on number of accounts and the balance. All the well known investment companies have 401K programs. Some of the benefit management companies can also coordinate the 401K program. The more investment options, the higher the cost, but they can start small.
Obviously matching costs the company money. Some of the companies contributed profit sharing to the 401K accounts, which also helped to encourage participation.
I have never been with a small company when they added a 401K, but one took the suggestion of an employee to make small change that would make it even more popular. Much more money flowed in, and we reached the next pricing level faster.