Number of steps in worst Case
You arrange your 30 batteries in pairs, where each pair consists of either:


2 empty batteries
2 full batteries
1 full and 1 empty battery


If you have a pair with 2 empty batteries it follows, that there is also a pair of 2 full batteries, thus, you have to test at most all of the pairs (15 steps) until you find a pair of two full batteries.

If your walkman isn't working after testing all 15 pairs, you know that each pair consists of a full and an empty battery.
You take the first two pairs with batteries (a,b) and (c,d). You then try the pairings: (a,c), (a,d) and (b,c).
You have now tested 18 combinations and either one of them worked or (b,d) has to be a working pair. 

I don't know if this counts as 19 steps for your purposes (you have found 2 full batteries after 18 steps but the walkman is not running yet).