My experience with making the transition
For many years I was under the misapprehension that I didn't have enough time to write unit tests for my code. When I did write tests, they were bloated, heavy things which only encouraged me to think that I should only ever write unit tests when I knew they were needed.
Recently I've been encouraged to use Test Driven Development and I found it to be a complete revelation. I'm now firmly convinced that I don't have the time not to write unit-tests.
In my experience, by developing with testing in mind you end up with cleaner interfaces, more focussed classes & modules and generally more SOLID, testable code.
Every time I work with legacy code which doesn't have unit tests and have to manually test something, I keep thinking "this would be so much quicker if this code already had unit tests". Every time I have to try and add unit test functionality to code with high coupling, I keep thinking "this would be so much easier if it had been written in a de-coupled way".
Comparing and contrasting the two experimental stations that I support. One has been around for a while and has a great deal of legacy code, while the other is relatively new.
When adding functionality to the old lab, it is often a case of getting down to the lab and spending many hours working through the implications of the functionality they need and how I can add that functionality without affecting any of the other functionality. The code is simply not set up to allow off-line testing, so pretty much everything has to be developed on-line. If I did try to develop off-line then I would end up with more mock objects than would be reasonable.
In the newer lab, I can usually add functionality by developing it off-line at my desk, mocking out only those things which are immediately required, and then only spending a short time in the lab, ironing out any remaining problems not picked up off-line.
My advice
It seems like you have started off well, any time you are going to make big changes to your development workflow, you have to make sure that everyone is involved in making that decision, and ideally that most people have bought into it. From your question, it looks like you've got this right. If people don't have an enthusiasm for the idea, it is doomed to either fail or generate bad will.
Unless you can present a compelling business case, I would not recommend a ground up implementation of unit tests and specifications for your whole system. As I mention above, if a system isn't designed with testing in mind, it can be very difficult to write automated tests for it.
Instead I would recommend starting small and using the the Boy Scout Rule:
Always leave the campground cleaner than you found it.
If while you are implementing something on this codebase, you can identify the specific tests required to test the existing behaviour and transition from the old behaviour to the new, then you have both documented the change in spec and made a start on implementing units tests for your system.
Modules which you don't touch don't get unit tests, but if you aren't touching them then it is probably because they are already thoroughly tested in use and need no changes, or they are never used.
What you want to avoid is wasting a whole load of developer effort writing tests which are never going to be needed (YAGNI works just as well for test code as for production code *8'), never going to be used again and demoralise people into thinking that tests are useless after all.
Summary
Start small, build trust in the tests incrementally and gain business value from developing tests when and where they benefit your team the most.