With Protobuf, you still have the cost of constructing the objects,
and the cost of then serializing them. Cap'n Proto removes the latter cost. Serializing is generally the much more expensive step. It also turns out Cap'n Proto reduces the building cost by a fair amount, because the arena-style allocation needed to support zero-copy output also happens to be a lot cheaper and more cache-friendly, but that's somewhat of an accident.
For message-passing scenarios, Cap'n Proto is an incremental improvement over Protobufs -- faster, but still O(n), since you have to build the messages. For loading large data files from disk, though, Cap'n Proto is a paradigm shift, allowing O(1) random access.