Which is more fundamental: key-value or subject-predicate-object?
Following your simplicity argument (binary is more fundamental than octal), I'd say that key-value stores are more fundamental.
I think that Subject-Predicate is essentially a 'compound' or 'aggregate' key, so a subject-predicate-object store is a key-value store with additional requirements on the key (namely that it can be split into two).