There are two points to consider in answer to this question.
When taking on something the size of the Galactic Republic, one does not stop with Plan A.
The Separatists were standing against the Republic, and yes, they had a huge droid army. And, of course, the people responsible for procuring that army said it would wipe all the foes from the table. Who DOESN'T tell their customers/government that their solution solves all problems?
But Plan A can always fail. The Republic could end up getting the upper hand, or destroy stocks of the droid army, or find better ways to jam the commands, or find an exploit in the command and control system, or find a bug in their artificial intelligence that allows Republic soldiers to literally walk circles around the droid army.
As such, the Separatists had a Plan B (which just so happened to be right up Palpatine's alley), the Death Star. It would take much more time to build, and take many more resources than the droid army, but it would ALSO serve as a blockbuster weapon to break any stalemate they might have experienced in the future.
More than one group of people can work on separate plans at once.
There were likely many skunkworks projects being developed by the Separatists at this time, from Death Stars to toxic bantha fodder. ALL the ideas were on the table, and the more promising ideas were promoted to the top, even the far-fetched ones. Win, lose, or draw, a Death Star would be a handy thing to have, if it could be built.
LEGENDS: Superweapons were just a thing people did in that galaxy far, far away.
The Star Wars galaxy is FULL of superweapons, starting with Centerpoint Station and going on through multiple Death Stars, World Devistators, superlasers mounted on ships, etc., etc., etc. The Sith Empire had superweapons. The ancestors of our heroes centuries+ BBY had superweapons. The Tarkin doctrine wasn't so much a new plan that needed superweapons so much as it was an explanation on how a superweapon could be used to enforce fear.
Finally, a real life example:
The US Army was pretty confident that it could storm Japan; it was called Operation Downfall. Operation Olympic would capture the south third of Kyushu, using Okinawa as a stage. Six months later, Operation Coronet was planned to invade Kanto.
It was planned to be the largest amphibious operation in history.
Of course, the problem was that Japanese geography made planning the invasion simple; there was only really one good way to do it. And the Japanese knew it too. The Japanese empire planned an all-out defense of their main island. And as Japan slowly lost control over the Pacific, they were drawing back planning for that ultimate defense.
Casualty estimates ran into the millions for Allied soldiers. And the casualties on the Japanese side were even higher.
And this is just a conflict on one measly little planet in the spare bedroom of the galaxy.
Yes, even though the Separatist government used droids, not living beings, those droids do have a non-zero cost. It takes time and effort to build them, transport them, program them; any "conventional" operation would include massive losses on both sides.
But both these situations had a superweapon: on Earth, it was the Atom Bomb.
But, like the Death Star, the Atom Bomb wasn't some solution pulled out of the air at the end of the war. Development on an atomic bomb began during the war, with production running throughout, in a deadly race of fear that the other side would figure it out first.
Dropping the bombs ended the war with Japanese surrender, and lead to millions of soldiers NOT becoming casualties on the American side. (There was, of course, a death toll on the other side that should not be forgotten about.)
The key here is, the Death Star, like the Atomic Bomb, was hoped to be at least a backstop, if not a replacement, for massive losses in the droid army.