As soon as you allow digital signatures, you have unforgeable messages and Byzantine Generals is solved. No need for consensus algorithms, proof of work, or blockchains.
I think that statement would be correct if changed to “unforgeable messages with all same-side generals honest (and un-confused).
The problem you are describing is a different one, where there is no single commander and a group of generals needs to collectively decide on a plan. There signatures are indeed not sufficient. The way proof-of-work solves it is by randomly electing one of the generals to become commander for this decision round (i.e. 'it mines the block'). The random election is somewhat imperfect, leading to second order complexities such as probabilistic finality.