If I want to encrypt structured data composed of key-value pairs of strings, would it be an advantage to use an encoding that stores keys, values and their lengths, and is padded with random numbers?
Generally, no, this is not a good idea. A semantically secure cipher uses an IV or nonce (number used once, a unique number in a statically sized encoding) that randomizes the ciphertext in combination with the key used. There is therefore no need to randomize the data input (the "message") itself.
It very much depends on the mode of operation if the randomization of the message will actually fully randomize the data in the first place. In case of CBC mode a random block with the block size of an IV could be used as an alternative to a random IV. However, it would not really differ from using an IV in the first place; it will actually cost you one additional block to encrypt for no reason at all. On the other hand, if you consider the more modern CTR mode then the key stream will just be XOR-ed with the random input, and it won't influence the rest of the plaintext / ciphertext message. The random data would just be overhead without offering any benefit.
Modern authenticated modes just require a nonce, randomized or not. GCM mode for instance requires a 12 byte nonce. You can safely prefix the IV or nonce to the ciphertext (as the size is commonly known or configured in advance). Note that CBC mode requires an unpredictable (i.e. randomized) IV.