We investigate the formation of dust in a stellar wind during the red-supergiant (RSG) phase of a very massive Population III star with the zero-age main sequence mass of 500 M_sun. We show that, in a carbon-rich wind with a constant velocity, carbon grains can form with a lognormal-like size distribution, and that all of the carbon available for dust formation finally condense into dust for wide ranges of the mass-loss rate ((0.1-3)x10^{-3} M_sun yr^{-1}) and wind velocity (1-100 km s^{-1}). We also find that the acceleration of the wind driven by newly formed dust suppresses the grain growth but still allows more than half of gas-phase carbon to be finally locked up in dust grains. These results indicate that at most 1.7 M_sun of carbon grains can form in total during the RSG phase of 500 M_sun Population III stars. Such a high dust yield could place very massive primordial stars as important sources of dust at the very early epoch of the universe if the initial mass function of Population III stars was top-heavy. We also briefly discuss a new formation scenario of carbon-rich ultra-metal-poor stars considering the feedback from very massive Population III stars. ; Comment: 1 table, 4 figures, accepted for publication in the ApJ Letters