먹어보다 means to try a new food for the first time; to try out something new. Let me change your sentences a little to make the difference more extinct. Compare 김밥을 먹으려고 식당에 가요 and 김밥을 먹어보려고 식당에 가요. The first one means that you're going to the restaurant to get 김밥; the second one means that you're going to the restaurant to get 김밥, and that it would be your first time having it. The difference is between just eating and trying something for the first time. I hope I helped!