My fear is I interview, and for some reason I'm not a fit for the new
company, I'm digging myself into a hole at the job I currently have.
You should never plan on just interviewing with one company. If you're serious about leaving (and I personally think you should be; 10 days of combined sick/holiday time after 3 years is ridiculous) then you need to get serious about leaving. You interview with as many as you need to, until you find one that is a good fit.
My boss has already told me that it looks bad that I'm taking unpaid
time, and any additional unpaid time will go against my performance
review.
If you're serious about leaving, then what does a note in a performance review matter? It doesn't. And I suspect your boss is probably concerned that you may already have been using those days of unpaid leave to seek other employment, which is why he's discouraging you from taking any more. Some might consider that to be unethical behavior on the part of your employer.
Anyways, in addition to the suggestions made by Chris and Dave with respect to interviewing remotely or by phone, early or late in the day, and trying to schedule as many interviews together as possible (which are very good ideas), there is a possible alternative. You could cancel your request for paid leave during your honeymoon. That would free up several paid leave days, which you could use for interviews. Stick with the suggestions to line up multiple interviews, and schedule them for the same day or block of days. Do your interviews, being sure to either note that you need leave to cover your honeymoon or to arrange a start-date that is after your honeymoon.
Then in the best-case scenario you don't upset your employer by exceeding your allocated number of paid leave days and you get paid leave to cover your honeymoon from your new employer (and probably some awkward questions about why you're cancelling the leave request). In the more likely scenario you don't upset your employer by exceeding your allocated number of paid leave days and you take your honeymoon as unpaid time. And in the worst-case scenario (if none of the interviews work out) you'd have to take your honeymoon as unpaid leave with your current employer, and deal with whatever fallout comes from that. Which might not be fun, but you could use it to point out that it's their substandard allocation of personal days that made the unpaid leave necessary.
I also am opposed to lying to a current employer, so I don't want to
fabricate reasons for taking time off.
How do you feel about telling the truth creatively? It's not terribly inaccurate to describe a job interview as "an important errand that I can't do at any other time". Or "a pressing obligation that just came up". Or "something that I need to do for my own health and well-being".
As an aside:
The rationale being, I was given X number of days, and if I can't
manage to stay inside of that, then I'm unreliable.
That rationale is absurd. If they give you 10 days to cover both vacation and sick leave, then their reasoning implies that they either expect you to never get sick or to not take vacations, because that's essentially the only way to stay within such a paltry limit.