How do I setup a foreign key relationship based on two columns?
Yes, by adding a UNIQUE constraint (or a unique index) on the company table, using these 2 columns:

ALTER TABLE company
  ADD CONSTRAINT CompanyID_DepartmentID_UQ
    UNIQUE (CompanyID, DepartmentID) ;


Then you can add the foreign key:

ALTER TABLE [user]
  ADD CONSTRAINT Company_User_FK
    FOREIGN KEY (CompanyID, DepartmentID) 
    REFERENCES company (CompanyID, DepartmentID)  ;


Test at SQL-Fiddle


Minor comment: Since the table company has DepartmentID as the primary key, shouldn't it be called department table? (How do you call the table where the CompanyID is the primary key?)