The verb, to compliment, in the 1600s meant to treat ceremoniously or with formal courteously, but quickly took on the meaning of praise as there is not a big step between the two forms of behaviour.
As the giving of gifts is frequently an element of ceremonious occasions - eg visiting heads of state are always handed something or other - the adjective, complimentary, had become used to mean 'free' in the sense of tickets etc by the 19th century.
formal gifts are still sometimes labelled "with the compliments of the management" or something like that... the subtext is that they are giving you this to show what a nice person they think you are.