Корректно: с заведующим (чем?) лабораторией.

Согласно «Полному академическому справочнику» под ред. В. В. Лопатина, вместо дефиса должен употребляться знак тире в сочетаниях с приложением, если одна из частей содержит пробел, и в сочетаниях с приложением, если одна из частей в свою очередь является сочетанием с приложением и содержит дефис.

Таким образом, верно:  врач — детский кардиолог, врач — клинический миколог, заведующий здравпунктом — фельдшер, врач — акушер-гинеколог, врач — анестезиолог-реаниматолог, врач — сердечно-сосудистый хирург, медицинский оптик-оптометрист (слово медицинский относится к обеим частями названия специальности), провизор-стажер, врач — детский уролог-андролог, врач — судебно-психиатрический эксперт; заведующий структурным подразделением, отделом, отделением, лабораторией, кабинетом, отрядом (начальник структурного подразделения, отдела, отделения, лаборатории, кабинета, отряда и т. д.) медицинской организации — врач-специалист.

Если речь идет об отделе как структурном подразделении лаборатории, то правилен первый вариант: заведующий отделом лаборатории.

Правильно: заведующий лабораторией. Такие слова, как заведующий, управляющий, командующий (т. е. существительные, произошедшие из причастий), управляют творительным падежом.

Правильно: заведующему лабораторией.

Правильно: заведующий лабораторией.

Не нужна запятая перед словом "профессор".

Правильно: дело заведующей лабораторией.

Правильно, только вместо точки нужна запятая.

Правильно: заведующая лабораторией.