I receive part of my salary in Bitcoins.  The simplest way for a company to pay using Bitcoins is to make it an "after tax deduction elected by the employee".  My salary is $X USD.  The company already deducts payroll taxes, income taxes, and benefit premiums.  I elected (by written authorization) to have a certain amount of my salary paid in BTC.  The options my company gave me were a specific USD amount, a specific % of salary, or entire net (after withholding and deductions) amount.  

On Payday the company converts the USD amount to BTC using the volume weighted average exchange rate over the entire pay period.  Our company's program covers all costs and fees but a company could charge a reasonable fee for the service.  I am sure on a long enough timeline payroll companies like ADP will offer this.

Now there are other ways to do this but the advantage of doing it this way is that it is very simply for any company to implement.  All Payroll software allows post tax deductions.  The amount deducted becomes a credit on the company USD books and an equivalent debit is made on the company's BTC books.   The tax implications are already taken care of (other than any capital gains on rising value) as the taxes were based on gross salary.  The company can still deduct the entire cost of the employees salary with no changes to accounting.