A small PoW on each block, however for some reason it can be precomputed which allows you to precompute a spam attack (which has happened from the CEO of BrainBlocks recently..)

It's an interesting issue, although it's a good question if it is possible to stop network spam. Bitcoin's solution to network spam is to limit the amount of transactions and charge a fee, with the fee going up the higher the demand for a transaction.

I don't see this setup working with Nano, as much of the protocol is designed around not having fees. After all, deciding who gets the fees and splitting it (among top representatives?) causes even more processing on the network.

I've had concerns in this area as well, as far as I know the team performed some stress tests and the network can do 100+ transactions per second, maybe more. There is also a small computation that the hardware needs to perform before sending the transaction, which is only a small guard against spam but pretty useful.

afair peak of stress test on main network was >300TPS, on test network is was >1500TPS. there exists dedicated software to create wallets and transaction using GPU, just for stress testing.