Manually show that 3x3x3 works. Then, it's clear that you can make a 2x3 block, which means you can make any 3xn block for even n. Now, since we know we can fill the box, either m, n, or k is divisible by three, wlog it's m. Then, if n or k is even, we win, since we can make a 3xn block for even n. If not, separate the $m\times n\times k$ box into 3x3x3, 3x3x(m-3), 3x3x(n-3), 3x3x(k-3), 3x(m-3)x(n-3), 3x(m-3)x(k-3), 3x(n-3)x(k-3), and (m-3)x(n-3)x(k-3). Clearly, all of these except for the 3x3x3 have a multiple of 3 and another even side length, so we win.