Let me add another consideration to the company's side of the equation.
Not only is a 401K a tool for the company to make them competitive when recruiting employees among other companies that offer that benefit, it is also a good retention tool.
Most company's 401K plans include a vesting periodvesting period of at least 3 years, sometimes more. An employee that leaves the company before they are vested in the plan will have to give up some % of the employer matched funds in the account. This gives employees incentive to stick around longer and the company reduces the risk of turnover which can be costly in terms of training and recruiting.
This also factors into the reason why employers would rather give matching on the 401K than a simple pay raise. Some of those employees are going to leave during the vesting period anyway, and when that happens the employer got the benefit of motivating (extrinsically) the employee, but in the end got to keep some of the money.