When, through the U.S. censuses, the birthplace switches back and forth between France and Germany, it's very likely that the person was born in Alsace-Lorraine — an ethnic German enclave in France — and this location jibes with the family's tradition of their origin. 

1.  Marriage Record:

2.  1890 Census:  the 1890 Census Population Schedules were destroyed.

3.  1900 Census Index/Images (online at Genealogy.com, Image #29 of 113):  Greece Town, Monroe Co., NY, Roll 1072 (Book 2), p. 128A, SN 15, SD 19, ED 9, enumerated 28 Jun 1900, official enumeration date 1 Jun 1900 (extracted by Diana Gale Matthiesen):¤•

1900:  for an explanation of the column headings, please see What the Numbers in the Federal Census Mean (missing columns contained no data).

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

299

314

Paille Joseph

Head

W

M

Jan 1852

48

M

20

Ger

Ger

Ger

1860

40

Na

Blacksmith

0

Y

Y

Y

O

M

H

______ Rose

Wife

W

F

Aug 1856

43

M

20

8

5

NY

Ger

Ger

Y

Y

Y

______ George A

Son

W

M

Dec 1882

17

S

NY

Ger

NY

Blacksmith

0

Y

Y

Y

______ Rose C

Dau

W

F

Jul 1884

15

S

NY

Ger

NY

At School

8

Y

Y

Y

______ Mary L

Dau

W

F

Feb 1886

14

S

NY

Ger

NY

At School

8

Y

Y

Y

______ Frank J

Son

W

M

Jan 1889

11

S

NY

Ger

NY

At School

8

Y

Y

Y

Kraus Charles J

Boarder

W

M

Jul 1868

81

Wd

NY

Ger

Ger

Blacksmith

0

Y

Y

Y

Charles's birthyear and age do not jibe, but that is clearly what was written, so it's apparently enumerator error.

4.  1910 Census Index/Images (online at Genealogy.com, Image #70 of 180):  Ridge Road, Greece Twp., Monroe Co., NY, Roll 988 (Book 1), p. 185B, SN5B, SD 16, ED 12, enumerated 19 Apr 1910, official enumeration date 15 Apr 1910 (extracted by Diana Gale Matthiesen):¤•

1910:  for an explanation of the column headings, please see What the Numbers in the Federal Census Mean (missing columns contained no data).

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

*

92

95

Paille Joseph

Head

M

W

58

M2

29

Fr. French

Fr. French

Fr. French

1870

N

Eng

Blacksmith

own shop

Emp

Y

Y

O

M

H

______ Rose

Wife

F

W

54

M1

29

9

6

New York

Fr. French

Ger. German

Eng

None

Y

Y

______ Rose

Dau

F

W

25

S

New York

Fr. French

New York

Eng

Bookkeeper

Kodak works

W

N

0

Y

Y

______ Frank

Son

M

W

21

S

New York

Fr. French

New York

Eng

Blacksmith

home shop

W

N

0

Y

Y

N

______ Gertude

Dau

F

W

9

S

New York

Fr. French

New York

None

Y

Y

Y

Daily John

border

M

W

42

S

Mass

Mass

Mass

Eng

Blacksmith

W

N

0

Y

Y

Y

*Ridge Road

5.  1920 Census Index/Images (online at Ancestry.com, Image #3-4 of 21):  Little Ridge Road, Greece Town, Monroe Co., NY, Roll T625-1119, pp. 104A-104B, SN 2A-2B, SD 19, ED 13, enumerated 7 Jan 1920, official enumeration date 1 Jan 1920 (extracted by Diana Gale Matthiesen):¤•

1920:  for an explanation of the column headings, please see What the Numbers in the Federal Census Mean (missing columns contained no data).

1

2

3

4

5

6

7

8

9

10

11

12

16

17

18

19

21

22

23

24

25

26

27

28

*

X

37

39

Paille Rose

Head

O

W

F

W

63

Wd

Y

Y

NY

Germany

German

Germany

French

Y

None

______ Rose C

Dau

F

W

35

S

Y

Y

NY

France

French

NY

Y

Bookeeper

Kodak Co

W.W.

______ Gertrude M

Dau

F

W

18

S

Y

Y

NY

France

French

NY

Y

Bookeeper

Kodak Co

W.W.

[next page]

Paille Evelyn R

Gchild

F

W

9

S

Y

NY

NY

NY

Y

None

*Little Ridge Road

She should be Evelyn R. FOX (see 1930) — was originally FOXLUGER, but it was shortened to FOX.

6.  1930 Census Index/Images (online at Ancestry.com, Image #32 of 69):  484 Clay Avenue, Rochester City (Ward 10, Block No. 578), Monroe Co., NY, Roll T626-1450 (Book 1), p. 146B, SN 46B, ED 28-50, SD 9, enumerated 15 Apr 1930, official enumeration date 1 Apr 1930 (extracted by Diana Gale Matthiesen):¤•

1930:  for an explanation of the column headings, please see What the Numbers in the Federal Census Mean (missing columns contained no data).
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	24	25	26	27	28
*	484	88	89	Paille Rose	Head	O	7500	R	N	F	W	73	Wd	23	N	Y	NY	Germany	France	Y	None
				______ Rose C	Dau					F	W	44	S		N	Y	NY	France	NY	Y	Book keeper	Kodak Co	W	Y
				Fox Evelyn	GDau					F	W	19	S		N	Y	NY	NY	NY	Y	Filing Clerk	Office Supplies	W	Y
*Clay Avenue

7.  SSDI:  Social Security Death Index (online at RootsWeb.com; missing columns contained no data):

Name	Birth	Death	Last Residence	SSN	Issued	Post-em
Gertrude M Tracy	02 Mar 1901	Jun 1995	14619 (Rochester, Monroe, NY)	085-22-0226	NY	Y

8.  Emails from Paul Tracy.  Family tradition gives their origin as Alsace-Lorraine.

9.  Paul Tracy's Genealogy Web Site (FamilyTreeMaker site at Genealogy.com).