Try "With Recompile". I've only used it when the stored procedure is overly optimising and resulting in some queries being slow, but it could be your issue:

CREATE OR ALTER PROCEDURE [dbo].[users]
    @SEARCH VARCHAR(100)='',  -- Gloabl filter
    @PageNumber INT,
    @PageSize INT,
    @SortOrder VARCHAR(10),
    @SortColumn INT
WITH RECOMPILE
AS
BEGIN
END

After fixing "Cannot perform alter on 'dbo.users' because it is an incompatible object type." ( users is already an existing object?),

and "Incorrect syntax near '@RecordFrom'." (removing the , after DESC )

and, of course, the old-style JOIN is also fixed...

I created some sample data:

CREATE TABLE users (id INTEGER, name VARCHAR(100), email VARCHAR(100), department VARCHAR(100));

INSERT INTO users VALUES
   (1,'Bill Clinton','bill@whitehouse.gov','unknown'),
   (2,'Ronald Reagan','ronald@whitehouse.gov','unknown'),
   (3,'Abe Lincoln','no-reply@whitehouse.gov','unknown');

I do have the following code which seems to work:

CREATE OR ALTER PROCEDURE [dbo].[usersXYZ]
    @SEARCH VARCHAR(100)='',  -- Gloabl filter
    @PageNumber INT,
    @PageSize INT,
    @SortOrder VARCHAR(10),
    @SortColumn INT
AS
BEGIN
    SET NOCOUNT ON

    BEGIN TRY
        DECLARE @RecordFrom INT ;
        SET @RecordFrom = (@PageNumber-1) * @PageSize;
 
        ;WITH CTE_Result (id, name, email, department) AS
        (
            SELECT * 
            FROM dbo.users
            WHERE 1=1 
              AND (@SEARCH = '' OR (@SEARCH != '' AND (
                                    name LIKE '%' + @SEARCH + '%' 
                                    OR email LIKE '%' + @search + '%'   
                                )))
        ), 
        CTE_Count AS 
        (
            SELECT COUNT(id) AS TotalRecords 
            FROM CTE_Result
        )
        SELECT *
        FROM CTE_Result
        CROSS APPLY CTE_Count
        ORDER BY
            CASE WHEN @SortColumn = 1 AND @SortOrder = 'asc' THEN id 
            END ASC,
            CASE WHEN @SortColumn = 1 AND @SortOrder = 'desc' THEN id END DESC 
            OFFSET @RecordFrom ROWS 
            FETCH NEXT @PageSize ROWS ONLY
    END TRY
    BEGIN CATCH
        THROW;
    END CATCH

    SET NOCOUNT OFF
END

output (2 of the 3 record in my test data):

when querying: EXEC [usersXYZ] 'a',1,10,"1",5

see: DBFIDDLE