How many colors exist? How many "colors" do exist? 
Our perception:
As far as I know, colors are just different frequencies of light. According to wikipedia, we can see wavelengths from about 380 nm und 740 nm. This means we can see light with a frequency from about $4.051 \cdot 10^{14}$ Hz to about $7.889 \cdot 10^{14} $ Hz. Is this correct? I don't know if time (and frequencies) are discrete or continuous values. If both are continuous, an uncountable number of "colors" would exist. If it is discrete, there might still exist no upper bound.
An upper bound? I found the article Orders of magnitude of frequencies. The Planck angular frequency seems to be by far higher than all other frequencies. Is this the highest frequency which is possible? Do higher frequencies make sense in physics?
Why do I ask this question: I am imagining the vector space $\mathbb{R}^4$ like the $\mathbb{R}^3$, but with colors. I need an infinite amount of colors if this should make sense. In fact the number has to be uncountable.
 A: If you are considering human vision there is a definite (and surprisingly small) number of distinguishable colors.
This is known as a MacAdam diagram and shows a region around a single color, on a chromaticity plot, that is indistinguishable from the color at the center.
The total number of colors would be the number of ellipses needed to completely fill the color space.  Obviously this depends on the individual's age, sex, lighting, etc

A: A human eye may only distinguish thousands or millions of colors – obviously, one can't give a precise figure because colors that are too close may be mistakenly identified, or the same colors may be mistakenly said to be different, and so on. The RGB colors of the generic modern PC monitors written by 24 bits, like #003322, distinguish $2^{24}\sim 17,000,000$ colors.
If we neglect the imperfections of the human eyes, there are of course continuously many colors. Each frequency $f$ in the visible spectrum gives a different color. However, this counting really underestimates the actual number of colors: colors given by a unique frequency are just "monochromatic" colors or colors of "monochromatic" light. 
We may also combine different frequencies – which is something totally different than adding the frequencies or taking the average of frequencies. In this more generous counting, there are $\infty^\infty$ colors of light where both the exponent and the base are "continuous" infinities.
If we forget about the visibility by the human eye, frequencies may be any real positive numbers. Well, if you're strict, there is an "academic" lower limit on the frequency, associated with an electromagnetic wave that is as long as the visible Universe. Lower frequencies really "don't make sense". But this is just an academic issue because no one will ever detect or talk about these extremely low frequencies, anyway.
On the other hand, there is no upper limit on the frequency. This is guaranteed by the principle of relativity: a photon may always be boosted by another ditch if we switch to another reference frame. The Planck frequency is a special value that may be constructed out of universal constants and various "characteristic processes" in quantum gravity (in the rest frame of a material object such as the minimum-size black hole) may depend on this characteristic frequency. But the frequency of a single photon isn't in the rest frame and it may be arbitrarily high.
A: The colors which are perceived by people are defined by the degree to which the light will excite the red,green, and blue photoreceptors in the cone cells of the eye. There are only three discrete colors we can perceive, and they are red, green, and blue. The statistics of the relative and absolute excitations, the amount of red,green, and blue averaged over many cells and over many time steps, defines the perceptual color space. It is somewhat vague, because the longer you average, and the more cells you have to average over, the finer you can distinguish the colors. But the gradiations become pointless after a certain amount of refinement.
The wavelengths of light are not in any way primary, the response of the three photoreceptors is. The reason different wavelengths have different colors is because they excite the different receptors differently.
This means that there is a three dimensional subspace of colors, which is defined by the degree to which the brain can integrate the signal for red,green, and blue, and determine the intensity of each component. The only way to be sure of the number of gradations of each is to do psychological testing: look at a division of the intensity scale for a pure color (a color which excites only one of the photoreceptors) and see how close the intensity can be before neighboring intensities cannot be reliably distinguished. It is probably between 255 and 512 steps for red and green in the standard range of a monitor, and between 100 and 256 for blue (this is a guess based on my own memories of my own perception). This is in the standard "octave" of a computer screen (the screen is not close to blinding, nor is it ever barely visible, but the eye is logarithmic, so this range should be the same in the total number of octaves, at most 10, I'll say about 4, and more for red/green then for blue, so that the right estimate is about 1000^3, or a billion colors.
But this does not take rhodopsin response into account. The rhodopsin response is separate from the color response, because the rhodopsin range is overlapping with all three receptors. If you include rhodopsin as separate, you would have to multiply by another 1000 possible values, or a trillion colors. Some of these colors would only be accessible by artificial means--- you would have to stimulate rhodopsin without stimulating the red, green, or blue phosphors, and this might be possible chemically, like if you have taken a psychoactive drugs, dream states, oxygen deprivation. Another way might be to use afterimages, which will remove the sensitivity of certain receptors.
A: While a specific frequency of light has a color, it does not uniquely define that color. Human eyes have 3 different "color" receptors, each of which is more sensitive to some freqencies than others. See this image.
There are an infinite number of colors, but there is probably some limit as to how finely a person can distinguish between different intensities coming from each type of photoreceptor.
A: First, the color is determined by the spectrum of the electromagnetic radiation in the visible range. Most colors cannot be produced by a single frequency. On the other hand, not every spectrum gives a different color, because we only have three different receptors in our eyes (actually there are four, but one type is not used for determining color). Therefore the complete color reception is based on a three-dimensional space (this is why almost all color spaces, like RGB, HSV, HSB, YUV have three parameters). Note however that despite of this, it is not true that all colors can be generated by mixing just three colors (you can describe all colors in e.g. sRGB, but then you need negative values for some colors). This is because not all activation patterns of the receptors can be produced by light. Indeed, all spectral colors (that all colors which correspond to light of just one fixed frequency) cannot be mixed from anything else. Also note that this three-dimensional space also contains the brightness (the HSV, HSB and YUV color spaces separate that out as a specific coordinate), therefore if you factor that out, the true color space has only two parameters left.
However, we cannot distinguish arbitrary close colors, therefore the true color spectrum is actually finite. However there's no way to strictly define the number of colors; indeed the translation of spectra into colors is not as well defined as the above would make you think. For example, our perception makes a white balance (that's why in analog photography the colors look wrong if you made e.g. a photo in electric light with daylight film, and why digital cameras come with automatic white balance), also of looking for a longer time at the same color at sufficient brightness, the receptors get "tired" (that's why if you then look at a white wall, you'll see the image in complementary colors). Also certain patterns of intensity change are perceived as colors. In other words, whatever you do will only be an approximation to true color perception.
A: 
How many colors exist?

None. 

Our perception: As far as I know, colors are just different frequencies of light. According to wikipedia, we can see wavelengths from about 380 nm und 740 nm. This means we can see light with a frequency from about 4.051⋅10^14 Hz to about 7.889⋅10^14 Hz. Is this correct? 

As far as I know, yes. Though I will add that some people can see into the ultra-violet a little. I imagine some can see into the infra-red a little too. 

I don't know if time (and frequencies) are discrete or continuous values. If both are continuous, an uncountable number of "colors" would exist. If it is discrete, there might still exist no upper bound.

As far as I know a wavelength or frequency can take any value, and the vary smoothly. 

An upper bound? I found the article Orders of magnitude of frequencies. The Planck angular frequency seems to be by far higher than all other frequencies. Is this the highest frequency which is possible? Do higher frequencies make sense in physics?

I think there could be some kind of upper bound to a photon frequency, due to a speed-of-light limitation. But I can't prove it. And it's way beyond the UV cutoff, so I don't think it's relevant.  

Why do I ask this question: I am imagining the vector space R4 like the R3, but with colors. I need an infinite amount of colors if this should make sense. In fact the number has to be uncountable. 

You might say that, but when you said How many colors exist? I said none. Because light exists, and this light has a wavelength, a frequency. But colour is a quale. It only exists inside our head. So in truth, it doesn't exist at all.
