1520s, from butter (n.) + milk (n.). Compare German Buttermilch, Dutch botermelk. It is what remains after the butter has been churned out.
butter-bean
buttercup
butter-fingered
butterfingers
butterfly
buttermilk
butternut
butterscotch
buttery
butthead
butthole