Don't know much about Nostr, but wondered re the spam problem, if it would make sense to introduce the idea of proof-of-work for the identities? A quick search shows that the have optional PoW proposals for notes (i.e., individual posts), but I didn't see anything about PoW for identities . People could spend $1, or $5, or $50 of compute for an identity, and others could use the cost of the identity as a filter. Havi…
Identity on nostr is just a public/private keypair.
You can enhance that identity by sending a kind0 (metadata) note with your name, bio, pictures. So i guess you're suggestion to add PoW for kind0 events which is covered by NIP13 too.