You might be able to find a book at your library with some ideas in it. I have one that has some great things in it. At the moment, I can't find it, but off the top of my head I've come up with these.
You can do lots of things with just a paring knife. I've done birds out of apples. You cut a shallow V out of one long side of the apple. This becomes the back of the bird. You turn the piece you take out around and attach it to the stem end of the V with a toothpick to become the neck of the bird. On either side of the V you cut a series of V's, one inside of the other. These become the wings when you spread them towards the blossom end of the apple. Cut off a piece on the bottom side of the bird so that it will sit flat. You can cut a section off of this to make the head. This seems to work best with delicious apples because of their longer shape.
You can make an easy palm tree out of a carrot and a green peeper. Cut the large end of the carrot so that it stands flat. Cut small notches into the carrot all around it and all the way to the top so that they look like the rough bark of a palm tree. (It's best to cut the notches from the top down so that when they open they will look more realistic.) Put the carrot in ice water to help open the notches while you make the leaves. Cut the stem and seeds out of the green pepper. Cut the pepper into three or four sections, leaving the pieces attached at the end. Cut the sections along the edges so that they look like palm branches, by making them come to a point at the end and notching the sides. Attach the leaves to the trunk with a toothpick. To help this stand up, you might want to cut a potato in half lengthwise. Set the potato on the flat side and attach the tree with a toothpick to the rough side. Instant desert island!
You can also make carrot curls using the peeler. Make long thin slices out of the carrot with the peeler. Form a curl out of each slice and secure with a toothpick. Drop into a bowl of ice water to "set" the curl. When ready to serve, remove from water, dry and take out the toothpick.
Carrot "flowers" can be made by cutting V's into the length of the carrot so that when you look at it from the end it resembles a flower. Usually 5 large V's work well, and if you want to have fancier flowers you can cut smaller V's into the center of each "petal". Then you just slice the carrot into coins like you would to cook them, and you'll have a whole bunch of flowers for garnish, or you can stir-fry them with other veggies to make your dinner more attractive.
Tomato roses can be made by peeling the tomato using fairly wide strips and slightly moving the knife to give a slightly wavy or rounded top to the peeling. When you've finihed peeling the tomato, start curling the peel around on itself so that it will resemble a rose. Make the inner part tight, and allow the outer section to be looser so that it will look like an open rose. This works best with a slightly firm tomato, and try to get a small amount of the flesh to give it some support.
If you have any questions, please feel free to pm me.