Magical Balloons

Alright, time to make a post so that I have at least managed to keep up 1 a year. I have a new puzzle Ben gave me ages ago, but I still haven't solved it and would feel wrong posting it when I have no ready solution. In the meantime, here is a puzzle I got from Tanya Khovanova's Math Blog:
You have 4 balloons (blue, red, green, and yellow, if you like) and some of them might be magical. You have a machine that you may put any number of balloons in and it will tell you how many balloons inside are magical. Find all the magical balloons using the machine not more than 3 times.

If you like you can also generalise, replace 4 with N and 3 with K, for which K can you solve the N balloon problem?