Wouldn't 'cāseī' (singular genitive) here be correct instead of the singular accusative 'cāseum'?
My mistake. Olet takes the accusative not only in the sense of 'to smell something', but also in the sense of 'to smell of something'.
So 'Marcus caseum olet' can mean either 'Marcus smells cheese' or 'Marcus smells of cheese'. However in the above case with 'valde', I guess 'of cheese' makes the most sense.