Taking away the worries
Would the provided "Prefix: " provide a weakness that can be exploited?
No, any secure cipher should be protected against plaintext attacks. To be precise, the ciphertext should be indistinguishable (not leak any info) for Chosen Plaintext Attacks. This is abreviated to IND_CPA. This is a stronger notion than just a known plaintext: it lets the attacker choose the plaintext message.
Would providing the suffix of each key result in a weakness?
No, keys of symmetric ciphers should generally consist of random bits. Random means that there is no relation between the various bits within the key. As there should be no relation, it should be impossible to get any information about other parts of the key.
Obviously this is not just a property of the cipher but it should also be a property of the key generation method. As the key consists of random bits, the key generation method is simply the random number generator used. So you must use a well seeded PRNG (e.g. simply
/dev/urandom on Posix machines).
This is also true for, for instance HMAC, in case you follow e-sushi's advice and use a hash based Key Derivation Function (KDF) instead of a chained cipher.
Can encryption algorithms be used daisy chained like this to create a simple computational puzzle / which encryption algorithms would be ideal for the task?
Yes, you can daisy chain them, but please read on.
There is no specific encryption algorithm that makes more sense. If you really want to use a cipher you could use the cipher to create a MAC algorithm (AES/CBC-MAC or AES-CMAC) and chain that.
AES would be preferable simply because there are plenty of platforms that accelerate the block cipher. With regards to compatibility with your goal: any modern cipher will do; neither of your algorithms have been broken and all use a large block size, which would be beneficial to the task.
In that sense, Threefish would be a good choice because of the large block size. That block cipher was designed for chained use in hash-like algorithms, mainly Skein of course.
Unless your goal is to let people try different symmetric algorithms there is no good reason to choose different algorithms; you might as well just choose one block cipher and use it multiple times.
Block chain technology, which this is a clear example of, is usually based on hash functions as e-sushi already mentions - in that case the goal is usually to find a specific pattern of bits (prefixes of 1 bits) in the randomized output of the hash functions - the benefit is that you can easily tweak the amount of output bits that you are looking for to increase or decrease the time looking for the answer.
Then again, the time required to find anything is randomized as well, so although you can tweak the difficulty the time to find the answer is undefined (i.e. you can only tweak the average time to find one or more answers).
A password based key derivation function (PBKDF) such as bcrypt, scrypt, PBKDF2 or Argon2 makes more sense if you're looking for more control for the time to find an answer.