According to the CGI article on Memory Alpha:
The very first CGI used was in Star Trek II: The Wrath of Khan, where Lucasfilm Graphics Group, then a subsidiary of Industrial Light & Magic (ILM), was responsible for the "Project Genesis" demonstration sequence effect, the very first fully textured 3D CGI representation shown in the motion picture business to a general public.
So per to the article, which is thoroughly detailed on the use of CGI in the franchise, the first use of a fully textured 3D CGI then would be the Genesis Effect, seen here (1982):
As luck would have it, there's actually "making of" video available on youtube:
