Holidays, annual leave, etc., there are entirely for you to do with as you wish. Whether you spend them interviewing for better jobs, or drinking cocktails on the beach in Barbados, that's nobody's business but your own.
So I think absolutely you should feel OK spending them on your job search.
Now there are a couple of caveats:
- If you're leaving your teammates in the lurch by taking time off without giving an amount of warning that is deemed acceptable in your workplace, that's a different matter. Whatever your official policies and accepted practices are regarding giving notice of leave, you should stick to them.
- And taking fake sick days to interview (while an extremely common practice) is not particularly ethical. You don't want to burn any bridges on your way out the door, so don't leave them remembering you as the guy who took a bunch of sickies to go to interviews, then stood there and bare-facedly said "yeah I had the flu" to his boss.
But using your personal leave entitlements to job-hunt is not something any reasonable person could object to.