"These eggs are not fresh."
Yes, that is the traditional character of the form 鲜. In traditional characters, the sentence is 這些雞蛋不鮮。
Hm... not to the nitpicking me. Only for describing the taste I leave out 新.
I believe you can say that, but the meaning is a little different. In that case 很 distinctly means "very" (it's not a filler word.) 这些鸡蛋不新鲜。=These eggs are not fresh. 这些鸡蛋不很新鲜。=These eggs are not very fresh. (So maybe the eggs are somewhat fresh?)