Why do Type II Restriction Endonucleases cleave at palindromic sequences? Type II Restriction enzymes usually cut only at palindromic sequences. Is there any specific reason for that? Is there any advantage for bacteria if they cleave phage DNA at this type of sequence?

First, not all restriction enzymes cut at palindromic sequences. A lot of them do though, simply because it is more effective. Recognising a palindromic sequence enables them to cut both strands of DNA at the "same" site, because the strand will have the same sequence only in different directions at that site.

See Wikipedia for example.