The TV series is set before the 2011 movie in which he meets Kitty for the first time.
I wanted to set the show earlier in Puss's life, back when he was the only one who thought he was a legend. When he had more to prove, and maybe wasn't quite so awesome at everything yet. So the series is set before the Puss In Boots movie, which in turn is set before the Shrek movies.
The Puss In Boots movie has a lot of spaghetti western elements, and we leaned further in that direction. We didn't want to go full fairytale, because the Shrek franchise really has that arena pretty well sewn up. Also, the Shrek movies have already used practically every well-known fairytale character there is, and since our series is set before those movies we couldn't use any of those characters. So it felt like we needed to go somewhere else.
Interview: Netflix's 'Puss In Boots' Series Creator On Secrets, Surprises & Why You Have To Watch
As to what happened to Dulcinea, the fate of his relationship with her wasn't confirmed in the show. All we know is that by the time he meets Shrek, he's single again. Presumably they broke up.