Yes, Paula was going to fire Kate if Nick took her job.
Nick is originally offered a job as a sou-chef to fill in when Kate is grieving the death of her sister.
The night that Kate calls in to spend the day with Zoe, Nick and Paula talk and Paula offers Nick a permanent position.
Paula You've really mastered the menu, Nick. You put your signature on the dishes, and all the regulars have noticed. How would you like to stay on permanently?
Nick I think I'd like that.
Source
Yes, Paula was planning on firing Kate if Nick excepted her offer. Kate begins to notice Paula paying more attention to Nick and asking him to do more things and confronts him. Nick then admits to Kate that he was offered her job.
Nick "She offered me your job."
Kate "What?
Kate "Why didn't you tell me?"
Paula clearly shows a lot of distaste in Kate throughout the film, especially with her short fuse for customers. This is shown in the beginning when Kate confronts one who complains and once again toward the end when Kate slams a raw steak down on a customer's table. Paula also forced Kate to see a therapist or she was going to be fired. So it is no surprise that Paula offered Nick her job.