The story
From kind (“inherent quality, nature”, noun) + -less. Compare Middle English kindelæs (“incapable of generation, barren”). The sense "destitute of kindness" is likely influenced by kind (“benevolent; affectionate”, adjective).
Etymology from Wiktionary, CC BY-SA 4.0.