Is there a way to greatly increase the time a brute force attack would require to decrypt the message without increasing the key size?
Something tells me you haven't understood what "brute force attack" means. In short, it boils down to: "try every possible key until you guess the correct one".
As a logic consequence, enlarging plaintext or ciphertext does not add anything to the security of a cipher when it comes to brute force attacks. Your cipher would still rely on the security of that
…small key size (say 40-bits)…
which is definitely too short to make brute-force attacks unfeasible.
Now, instead of thinking about increasing plaintext and/or ciphertext message sizes (which might even introduce additional attack vectors which could void the need for a brute force attack), we usually fall back on KDFs (key derivation functions) to get a stronger key.
Differently worded: instead of trying to make the "message" stronger (which doesn't really make sense), we make the "secret" stronger as that actually adds to security… thanks to the algorithm design of KDFs (with tweakable parameters et al).
Think of it this way — a burglar (read: attacker) doesn't care how big or small your house (read: message) is. All that counts is the strength of the lock (read: cryptographic algorithm) and the strength of the key. A good lock and key can keep a small toolshed in your backyard safe, while a bad lock with an easy to reproduce key can make a military bunker as accessible as a public park bench.
To wrap it up, the security of a cipher mainly* comes from:
- the individual cryptographic algorithm used, and
- the key, which should be strong/large enough to make it unfeasible to simply "walk all keys until you stumble upon the correct one" (which is what we call a "brute force attack")
When not enough key material is available, KDFs come handy. And in case the cryptographic algorithm doesn't support an accordingly strong key size, you should switch the algorithm for a stronger one. There are ample, well-vetted algos availabe.
* Nota bene: Surely there are some additional nit-bits like initialisation vectors etc that also add to the security of modern ciphers, but I've bluntly skipped all that to keep this answer short and simple.